[BZOJ 4129]Haruna’s Breakfast

。。OTZ终于写过了

树上待修改莫队

错误点大概有三个

1.p和q搞混了，以后不要用这两个变量

2.size[u] += size[v]不知道什么时候被吃掉了

3.B = sqrt(n) + 1

#include 
   
   
    
    

using namespace std;
#define maxn 100010

int P[maxn];
int c[maxn];
bool is[maxn];
struct Block{
    int vis[1000], sum, cnt, l, r, wy;
    void build(int l, int r){
        this->l = l, this->r = r;
        wy = l-1;
        sum = r - l + 1;
    }
    void update(int u){
        int t = c[u] - wy;
        if(!is[u]){
            vis[t] --;
            if(vis[t] == 0)cnt --;
        }
        else{
            if(vis[t] == 0)cnt ++;
            vis[t] ++;
        }
    }
    bool empty(){return sum == cnt;}
    int ask(){
        for(int i = 1; i <= sum; i ++)
            if(!vis[i])return i + wy;
    }
}blo[1000];

int n, m;
struct Edge{
    int to, next;
}edge[maxn << 1];

int h[maxn], cnt;
void add(int u, int v){
    cnt ++;
    edge[cnt].to = v;
    edge[cnt].next = h[u];
    h[u] = cnt;
}

int dfn[maxn], dfs_clock, pos[maxn];

struct opt{
    int u, v, id, t;
    bool operator<(const opt& k)const{
        if(pos[u] != pos[k.u])return dfn[u] < dfn[k.u];
        if(pos[v] != pos[k.v])return dfn[v] < dfn[k.v];
        return t < k.t;
    }
}q[maxn], p[maxn];
int qnt, pnt;

const int root = 1;


int fa[maxn], dep[maxn], B, tim, size[maxn];
stack
    
    
     
     S;
void dfs(int u){
    dfn[u] = ++ dfs_clock;
    dep[u] = dep[fa[u]] + 1;
    S.push(u);
    for(int i = h[u]; i; i = edge[i].next){
        int v = edge[i].to;
        if(v == fa[u])continue;
        fa[v] = u;
        dfs(v);
        size[u] += size[v];
        if(size[u] >= B){
            ++ tim;
            for(;;){
                v = S.top();
                if(v == u)break;
                pos[v] = tim;
                S.pop();
            }
            size[u] = 0;
        }
    }size[u] ++;
}
int anc[maxn][20];
void pre_LCA(){
    memset(anc, -1, sizeof anc);
    for(int i = 1; i <= n; i ++)
        anc[i][0] = fa[i];
    for(int j = 1; 1<
     
     
      
      <= n; j ++){
        for(int i = 1; i <= n; i ++){
            int a = anc[i][j-1];
            if(~a)anc[i][j] = anc[a][j-1];
        }
    }
}
#define log Log
int log;
int ask_LCA(int p, int q){
    if(dep[p] < dep[q])swap(p, q);
    for(log = 1; 1<
      
      
       
       <= dep[p]; log ++);log --;
    for(int i = log; i >= 0; i --)
        if(~anc[p][i] && dep[anc[p][i]] >= dep[q])
            p = anc[p][i];
    if(p == q)return p;
    for(int i = log; i >= 0; i --)
        if(~anc[p][i] && anc[p][i] != anc[q][i])
            p = anc[p][i], q = anc[q][i];
    return fa[p];
}

int ans[maxn], last[maxn], pre[maxn];

void Xor(int u){
    is[u] ^= 1;
    if(c[u] > n)return;
    blo[P[c[u]]].update(u);
}

void Move(int u, int v){
    while(u != v){
        if(dep[u] < dep[v])swap(u, v);
        Xor(u); u = fa[u];
    }
}

int ask(){
    for(int i = 1; i <= B; i ++)
        if(!blo[i].empty())
            return blo[i].ask();
}

void Modify(int u, int v){
    if(is[u]){
        Xor(u);
        c[u] = v;
        Xor(u);
        return;
    }
    c[u] = v;
}

int main(){
    scanf("%d%d", &n, &m);
    B = sqrt(n) + 1;
    for(int i = 1; i <= n; i ++)
        scanf("%d", &c[i]);
    int u, v, d;
    for(int i = 1; i < n; i ++){
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs(root); ++ tim;
    for(;!S.empty(); S.pop())pos[S.top()] = tim;
    pre_LCA();
    for(int i = 1; i <= m; i ++){
        scanf("%d%d%d", &d, &u, &v);
        if(!d){
            ++ pnt;
            p[pnt].u = u;
            p[pnt].v = v;
            p[pnt].t = pnt;
        }
        else{
            ++ qnt;
            q[qnt].u = u;
            q[qnt].v = v;
            q[qnt].id = qnt;
            q[qnt].t = pnt;
        }
    }

    for(int i = 1; i <= B; i ++){
        int L = (i-1) * B + 1, R = i * B;
        R = min(R, n);
        if(i == 1)L = 0;
        for(int j = L; j <= R; j ++)
            P[j] = i;
        blo[i].build(L, R);
        if(R == n){
            B = i;
            break;
        }
    }

    for(int i = 1; i <= n; i ++)
        last[i] = c[i];
    for(int i = 1; i <= pnt; i ++){
        pre[i] = last[p[i].u];
        last[p[i].u] = p[i].v;
    }

    sort(q+1, q+1+qnt);
    int l = 1, r = 1, t = 0, LCA;
    for(int i = 1; i <= qnt; i ++){
        while(t < q[i].t)t ++, Modify(p[t].u, p[t].v);
        while(t > q[i].t)Modify(p[t].u, pre[t]), t --;
        Move(l, q[i].u), Move(r, q[i].v);
        l = q[i].u, r = q[i].v;
        LCA = ask_LCA(l, r);
        Xor(LCA);
        ans[q[i].id] = ask();
        Xor(LCA);
    }

    for(int i = 1; i <= qnt; i ++)
        printf("%d\n", ans[i]);

    return 0;
}