考试遇到一道题：

有一棵n个点的有根树，每个点有一个颜色，每次询问给定一个点\(u\)和一个数\(k\)，询问\(u\)子是多少个不同颜色节点的\(k\)级祖先。n<=500000。

显然对每一层建主席树可行，但还有更优雅的一种做法——\(DSU\)

所谓\(DSU\)，是一类处理子树信息的问题的通解(\(O(n\log n\))

其主要过程是树剖后，沿重儿子向下，优先统计轻儿子，并在统计结束后删除对轻儿子统计信息，最后删除对重儿子统计信息。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#define R(a,b,c) for(register int a = (b); a <= (c); ++a)
#define nR(a,b,c) for(register int a = (b); a >= (c); --a)
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define MP make_pair
#ifdef QWQ
#define D_e_Line printf("\n--------\n")
#define C_e(x) cout << (#x) << " : " << x << endl
#define D_e(x) cerr << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <assert.h>
#define TIME() fprint(stderr, "TIME : %.3lfms\n", (double)clock() / CLOCKS_PER_SEC)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
#define D_e_Line
#define D_e(x)
#define C_e(x)
#define Pause
#define FileOpen()
#define FileSave()
#define TIME()
#define dbg(...)
#endif
struct FastIO {
    template<typename ATP> inline FastIO& operator >> (ATP &x) {
        x = 0; int f = 1; char c;
        for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
        while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
        if(f == -1) x = -x;
        return *this;
    }
} io;
using namespace std;
template<typename ATP> inline ATP Max(ATP x, ATP y) {
    return x > y ? x : y;
}
template<typename ATP> inline ATP Min(ATP x, ATP y) {
    return x < y ? x : y;
}
template<typename ATP> inline ATP Abs(ATP x) {
    return x < 0 ? -x : x;
}
#include <vector>
#include <set>

const int N = 1e5 + 7;
const int base = 122777;

char str[27];
inline unsigned long long HashVal(char *str) {
    int len = strlen(str + 1);
    unsigned long long s = 1;
    R(i,1,len)
        s = s * base + str[i] - 'a';
    return s;
}
struct Edge {
    int nxt, pre;
} e[N];
int head[N], cntEdge;
inline void add(int u, int v) {
    e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;
}
struct Ques {
    int K, id;
    Ques(int _K, int _id) : K(_K), id(_id) {}
};
int ans[N];
vector<Ques> q[N];
set<int> tot[N];
unsigned long long val[N];
int son[N], dep[N], fa[N], siz[N];
inline void DFS_First(int u, int father) {
    dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;
    for(register int i = head[u]; i; i = e[i].nxt){
        int v = e[i].pre;
        DFS_First(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
bool big[N];
inline void Clear(int u, int father) {
    tot[dep[u]].clear();
    for(register int i = head[u]; i; i = e[i].nxt){
        int v = e[i].pre;
        if(big[v]) continue; // if it' s a heavy son, ignore it
        Clear(v, u);
    }
}
inline void Calc(int u, int father) {
    tot[dep[u]].insert(val[u]);
    for(register int i = head[u]; i; i = e[i].nxt){
        int v = e[i].pre;
        if(big[v]) continue;
        Calc(v, u);
    }
}
int n;
inline void DSU(int u, int father, int flag) { // flag = 0 : light, 1 : heavy
    for(register int i = head[u]; i; i = e[i].nxt){ // every light son
        int v = e[i].pre;
        if(v == son[u]) continue;
        DSU(v, u, 0);
    }
    if(son[u]) DSU(son[u], u, 1), big[son[u]] = true; // heavy son
    Calc(u, father);
    for(vector<Ques>::iterator it = q[u].begin(); it != q[u].end(); ++it){
        int t = dep[u] + it -> K;
        if(t <= n + 1) ans[it -> id] = tot[t].size();
    }
    if(son[u]) big[son[u]] = false; // finished getting the information from the heavy son
    if(!flag) Clear(u, father); // clear the information from the light son
}

int main() {
freopen("ancestor.in", "r", stdin);
freopen("ancestor.out", "w", stdout);
//FileOpen();
//FileSave();
    io >> n;
    R(i,1,n){
        scanf("%s", str + 1);
        val[i] = HashVal(str);
        int fa;
        io >> fa;
        add(fa, i);
    }
    int Q;
    io >> Q;
    R(i,1,Q){
        int x, K;
        io >> x >> K;
        q[x].push_back(Ques(K, i));
    }
    DFS_First(0, 0); 
    DSU(0, 0, 0);
    
    R(i,1,Q){
        printf("%d\n", ans[i]);
    }
    
    return 0;
}
/*
5 
alice 0 
alice 1 
bob 2 
cindy 1 
bob 2 
3 
2 1 
1 2 
1 1 
*/