CodeForces - 246E LCA+树上启发式合并

题目链接：https://codeforces.com/problemset/problem/208/E
题目大意：有一棵森林。每个节点一个姓名。每次询问x k:x的k级祖先处于deep[x]的儿子有多少个名字不同的节点

思路：和上题一样，只是把数组换成了map。

#include <bits/stdc++.h>
using namespace std;

vector<int> G[200005];
int id[200005];
int ans[200005], vis[200005];
map<string, int> mp;
map<int, int> c[200005];
string s[200005];
int tot=0;
int ID(string x){
    if(mp.count(x)){
        return mp[x];
    }
    mp[x]=++tot;
    return tot;
}
vector<pair<int, int> > q[200005];
int siz[200005], dfn[200005], son[200005], d[200005], how[200005], T=0;
void dfs(int u, int deep){
    vis[u]=1;
    siz[u]=1, dfn[u]=++T; d[T]=deep, how[T]=id[u];
    for(auto x: G[u]){
        dfs(x, deep+1);
        siz[u]+=siz[x];
        son[u]=siz[x]>siz[son[u]]?x:son[u];
    }
}

void DSU(int u, int k){
    vis[u]=1;
    for(auto x: G[u]){
        if(x!=son[u]){
            DSU(x, 0);
        }
    }
    if(son[u]) DSU(son[u], 1);
    for(auto x: G[u]){
        if(x!=son[u]){
            for(int i=0; i<siz[x]; i++){
                int now=dfn[x]+i;
                c[d[now]][how[now]]++;
            }
        }
    }
    c[d[dfn[u]]][how[dfn[u]]]++;
    for(auto x: q[u]){
        int k=x.first, pos=x.second;
        ans[pos]=c[k+d[dfn[u]]].size();
    }
    if(!k){
        for(int i=0; i<siz[u]; ++i){
            int now=dfn[u]+i;
            c[d[now]].erase(how[now]);
        }
    }
}

int main(){
    int n, x, k; scanf("%d", &n);
    for(int i=1; i<=n; i++){
        cin>>s[i];
        id[i]=ID(s[i]);
        scanf("%d", &x);
        if(x){
            G[x].push_back(i);
        }
    }
    int Q; scanf("%d", &Q);
    for(int i=1; i<=Q; i++){
        scanf("%d%d", &x, &k);
        q[x].push_back({k, i});
    }
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            dfs(i, 0);
        }
    }
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=n; i++){
        if(!vis[i]){
            DSU(i, 0);
        }
    }
    for(int i=1; i<=Q; i++){
        printf("%d\n", ans[i]);
    }

    return 0;
}
/*
6
0 1 1 0 4 4
1
5 1
*/