题解：P2720 小A的礼物

· · 题解

子树数颜色问题居然没有树上启发式合并的题解？

首先观察题面，2 到 n 的每一个点都有唯一的入边，保证点 1 能到达任意点，这不就是一棵只能往下走的树嘛。

那么，一个点能走到的位置也就是它子树内的所有节点了。也就是说，对于每一次询问的节点，我们要求出它子树内的不同礼物种类。

对于这个问题我们有一个很优秀的解法：树上启发式合并。

顾名思义，这种方法运用了启发式的思想。首先我们有朴素算法：对于每个节点，暴力统计出子树内的所有信息。

这个时候，有人开始发扬人类智慧，想到：之前的做法每次都要清空统计的数组，但是我们可以保留其中一个子树的信息，这样就可以少统计一部分了。那么保留哪个子树呢？显然是要保留大小最大的了，也就是重链剖分里的重儿子。

可以证明，按照这样的方式，每个节点被重复统计的次数等于它到根的轻边个数，而这个数是 O(\log n) 级别的，因此总时间复杂度即为 O(n \log n)。

代码非常好写，因为这其实就是一个暴力。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+6;
int n,m,ans[N],buck[N],cnt,a[N];
vector<int> f[N];
int fa[N],dep[N],son[N],siz[N];
void dfs(int x,int y){
    dep[x]=dep[y]+1; siz[x]=1;
    for(int u:f[x]){
        if(u==y) continue;
        dfs(u,x); siz[x]+=siz[u];
        if(siz[u]>siz[son[x]]) son[x]=u;
    }
}
void calc(int x,int son,int sgn){ //暴力递归统计子树
    if(!buck[a[x]]) cnt++;
    buck[a[x]]+=sgn;
    if(!buck[a[x]]) cnt--;
    for(int u:f[x]){
        if(u==son||u==fa[x]) continue;
        calc(u,son,sgn);
    }
}
void dfs2(int x,int flag){//flag表示该节点是否是重儿子，即是否要清空
    for(int u:f[x]){
        if(u!=fa[x]&&u!=son[x]) dfs2(u,0);
    }
    if(son[x]) dfs2(son[x],1);
    calc(x,son[x],1);
    ans[x]=cnt;//对于每个节点存下答案
    if(flag) return;//如果是重儿子，则跳过清空步骤
    calc(x,-1,-1);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;++i){
        cin>>fa[i];
        f[i].push_back(fa[i]);
        f[fa[i]].push_back(i);
    }
    for(int i=1;i<=n;++i) cin>>a[i];
    dfs(1,0); dfs2(1,1);
    cin>>m;
    for(int x,i=1;i<=m;++i){
        cin>>x; cout<<ans[x]<<'\n';
    }
    return 0;
}

希望这篇题解能够帮到你！