成都七中

给你一棵 \(n\) 个节点的树，每个节点有一种颜色，有 \(m\) 次查询操作。 查询操作给定参数 \(l\ r\ x\)，需输出： 将树中编号在 \([l,r]\) 内的所有节点保留，\(x\) 所在联通块中颜色种类数。 每次查询操作独立。

对于 \(100\%\) 的数据，所有出现过的数在 \([1,10^5]\) 之间。

题解

https://www.luogu.com.cn/blog/PurpleWonder/solution-p5267

大概来说，是有两次的问题转化的过程：

第一步

建出点分树，这样对于询问 \((l,r,x)\) 中 \(x\) 所在的一个连通块，必定完全包含在 \([l,r]\) 区间内某一个节点（在点分树上）的子树里面，在点分树上暴力跳父亲即可找到这个节点，然后把这个询问"送"给这个节点，接下来我们一个节点一个节点地处理这些询问。

这样转化之后，问题就变成了：在一棵树中，从根节点出发，只经过 \([l,r]\) 范围内的点，可以到达的颜色数。

第二步

我们记录一下每一个节点到（点分树上的）每个祖先的路径上的编号最大的点和编号最小的点，分别设成 \(L,R\)。

我们发现，只有对于 \(x\) 节点拥有的一个询问 \((l,r)\)，只有 \(L\geq l\) 且 \(R\leq r\) 的节点才能对答案有贡献。

于是，这就是一个二维偏序问题了……将询问离线一波，第一维排序第二维树状数组维护即可解决。

如何计算颜色数量呢？对每个颜色开个桶操作即可，贪心的选择更优（更可能被包含）的区间。

CO int N=1e5+10;
int n,m,col[N];
vector<int> to[N];

int vis[N],siz[N],all;
pair<int,int> root;
struct node {int l,r,id;};
vector<node> val[N],que[N];

void find_root(int u,int fa){
    pair<int,int> nrt={0,u};
    siz[u]=1;
    for(int v:to[u])if(!vis[v] and v!=fa){
        find_root(v,u);
        siz[u]+=siz[v];
        nrt.first=max(nrt.first,siz[v]);
    }
    nrt.first=max(nrt.first,all-siz[u]);
    root=min(root,nrt);
}
void dfs(int u,int fa,node x){
    val[u].push_back(x);
    que[x.id].push_back({x.l,x.r,col[u]});
    for(int v:to[u])if(!vis[v] and v!=fa)
        dfs(v,u,{min(x.l,v),max(x.r,v),x.id});
}
void divide(int u){
    vis[u]=1;
    dfs(u,0,{u,u,u});
    int oall=all;
    for(int v:to[u])if(!vis[v]){
        root={all=siz[v]<siz[u]?siz[v]:oall-siz[u],0},find_root(v,0);
        divide(root.second);
    }
}

int buc[N],cnt[N],ans[N];

void insert(int p,int v){
    for(int i=p;i<=n;i+=lowbit(i)) cnt[i]+=v;
}
int query(int p){
    int ans=0;
    for(int i=p;i;i-=lowbit(i)) ans+=cnt[i];
    return ans;
}

int main(){
    read(n),read(m);
    for(int i=1;i<=n;++i) read(col[i]);
    for(int i=1;i<n;++i){
        int u=read<int>(),v=read<int>();
        to[u].push_back(v),to[v].push_back(u);
    }
    root={all=n,0},find_root(1,0);
    divide(root.second);
    for(int i=1;i<=m;++i){
        int l=read<int>(),r=read<int>(),u=read<int>();
        for(CO node&x:val[u])if(l<=x.l and x.r<=r){
            que[x.id].push_back({l,r,-i});break; // negative id for querys
        }
    }
    for(int i=1;i<=n;++i){
        sort(que[i].begin(),que[i].end(),[](CO node&a,CO node&b)->bool{
            return a.l!=b.l?a.l>b.l:a.id>b.id;
        });
        for(CO node&x:que[i]){
            if(x.id<0) ans[-x.id]=query(x.r);
            else{
                if(buc[x.id]>x.r) insert(buc[x.id],-1),buc[x.id]=0;
                if(!buc[x.id]) insert(x.r,1),buc[x.id]=x.r;
            }
        }
        for(CO node&x:que[i])if(x.id>0)
            if(buc[x.id]==x.r) insert(x.r,-1),buc[x.id]=0;
    }
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}

LG5311 成都七中

原文：https://www.cnblogs.com/autoint/p/12323745.html