题解HAGA

题意：

给一棵大小为 n 的树，第 i 个节点上站着一个编号为 i 的人，第 j 条边只允许编号在 l_j,R_j 间的人通过，第 i 个人有 K_i 次机会强行通过一条边，分别求每个人可以到达的点的个数，n<=1e5,k<=1。

题解思路：

考虑第 i 个人时，连接所有可以让 i 通过的边,断开所有不可以让 i 通过的边，如果 K_i 等于 0 ，那么答案就是 i 号点所在的连通块的大小；如果 K_i 等于 1 则答案为 i 号点所在的连通块的大小加上所有与该连通块相邻的连通块的大小的和。那么我们只需要维护连通块的大小和相邻连通块大小和就可以了。

考虑如何加入一条边并维护信息。对于连通块的大小可以直接用并查集来维护，问题就在如何维护相邻连通块大小和。以任意一个点作为整棵树的树根，对于一个连通块，把相对树根深度最浅的点作为该连通块的顶点，由于所以的边原先都是树边，所以每一个连通块也都是树，而且只有顶点和叶子会和其它连通块接触。把顶点和叶子的贡献分开计算，对于和顶点相邻的连通块，只需要记录当前连通块的顶点是谁，然后找到在整棵树上顶点的父亲，得到该点所在的连通块的大小即可；对于和叶子相邻的连通块，记录它们的大小和，在合并两个连通块时，总是一个在上一个在下，只需要加上下面的连通块的与叶子相邻的连通块的大小和然后减去该连通块的大小即可。

连接一条边容易，但是删除一条边就比较困难，所以可以考虑线段树分治。把所有边所对应的编号区间挂到线段树上分成 O(log n)段，加入边时就记录一下当前被修改的数修改前的值，删除的时候就可以直接赋值回溯（所以上面使用的并查集不能用路径压缩要用按秩合并）。在叶子上统计每个人的答案即可。

时间复杂度: O( n log ^2 n )

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,h[N],ans,l,r,w,nw,rs[N],k[N],cnt;
int f[N],len[N],s1[N],s2[N],tp[N],fa[N];
struct P{int x,y;}p[N];
struct E{int l,to;}e[N<<1];
vector<int>V[N<<2];
void Ad(int z,int y,int c){
    if(z>r||y<l)return;
    if(z>=l&&y<=r){
        V[c].push_back(w);
        return;
    }
    int mid=z+y>>1;
    if(l<=mid)Ad(z,mid,c<<1);
    if(r>mid)Ad(mid+1,y,c<<1|1);
}
void dfs(int x){
    cnt++;
    f[x]=tp[x]=x;
    s1[x]=s2[x]=len[x]=1;
    for(int i=h[x];i;i=e[i].l){
        int to=e[i].to;
        if(to==fa[x])continue;
        fa[to]=x;
        dfs(to);
        s2[x]++;
    }
}
int fi(int x){return x==f[x]? x:fi(f[x]);}
struct His{
    int f,sn,fx,s1,s2,len,tp,s2f;
}hs[N];
void Del(His a){
    f[a.sn]=a.sn;
    s2[a.fx]=a.s2f;
    s1[a.f]=a.s1;
    s2[a.f]=a.s2;
    len[a.f]=a.len;
    tp[a.f]=a.tp;
}
void Clr(int d){
    while(nw>d)Del(hs[nw--]);
}
void Qr(int z,int y,int c){
    int hl=nw;
    for(int i=V[c].size()-1;i>=0;i--){
        int x=p[V[c][i]].x,y=p[V[c][i]].y;
        if(fa[x]==y)swap(x,y);
        x=fi(x);y=fi(y);
        int fx=fi(fa[tp[x]]);
        if(len[x]<len[y]){
            hs[++nw]=(His){y,x,fx,s1[y],s2[y],len[y],tp[y],s2[fx]};
            f[x]=y;
            tp[y]=tp[x];
            s2[fx]+=s1[y];
            s2[y]=s2[x]+s2[y]-s1[y];
            s1[y]=s1[x]+s1[y];
        }else {
            hs[++nw]=(His){x,y,fx,s1[x],s2[x],len[x],tp[x],s2[fx]};
            f[y]=x;
            (len[x]==len[y])&&(len[x]++);
            s2[fx]+=s1[y];
            s2[x]=s2[x]+s2[y]-s1[y];
            s1[x]=s1[x]+s1[y];
        }
    }
    if(z==y){
        int x=fi(z),fx=fi(fa[tp[x]]);
        if(k[z])rs[z]=s2[x]+s1[fx];
        else rs[z]=s1[x];
        Clr(hl);
        return;
    }
    int mid=z+y>>1;
    Qr(z,mid,c<<1);Qr(mid+1,y,c<<1|1);
    Clr(hl);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&k[i]);
    for(int i=1;i<n;++i){
        scanf("%d %d %d %d",&p[i].x,&p[i].y,&l,&r);
        w=i;Ad(1,n,1);
        e[i<<1]=(E){h[p[i].y],p[i].x};h[p[i].y]=i<<1;
        e[i<<1|1]=(E){h[p[i].x],p[i].y};h[p[i].x]=i<<1|1;
    }
    dfs(1);
    Qr(1,n,1);
    for(int i=1;i<=n;++i)printf("%d\n",rs[i]);
    return 0;
}

并查集信息也可以用Splay维护，时间复杂度 O（ n log n ）。