Codeforces Round #151 (Div. 2) E Blood Cousins Return

Blood Cousins Return

启发式合并

在跑启发式合并的同时，对每个深度都维护一个 \(set\)，就可以自动去重并计算有多少种不同的字符串

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
using namespace std;
const int maxn = 2e5 + 10;
#define pii pair<int, int>
int siz[maxn], dep[maxn], hson[maxn], fa[maxn];
int L[maxn], R[maxn], tp = 0, rnk[maxn];
vector<int>gra[maxn];
set<string>st[maxn];
string s[maxn];
int ans[maxn];
vector<pii>qs[maxn];
int n, m;

void dfs1(int now, int d)
{
    dep[now] = d;
    L[now] = ++tp;
    rnk[tp] = now;
    siz[now] = 1;
    hson[now] = -1;
    for(int nex : gra[now])
    {
        if(nex == fa[now]) continue;
        dfs1(nex, d + 1);
        siz[now] += siz[nex];
        if(hson[now] == -1 || siz[nex] > siz[hson[now]])
            hson[now] = nex;
    }
    R[now] = ++tp;
}

void dfs2(int now, int keep)
{
    for(int nex : gra[now])
        if(nex != fa[now] && nex != hson[now]) dfs2(nex, 0);
    if(hson[now] != -1) dfs2(hson[now], 1);
    for(int nex : gra[now])
    {
        if(nex == fa[now] || nex == hson[now]) continue;
        for(int i=L[nex]; i<=R[nex]; i++)
                st[dep[rnk[i]]].insert(s[rnk[i]]);
    }
    st[dep[now]].insert(s[now]);
    for(auto [d, id] : qs[now])
    {
        if(d + dep[now] <= n) ans[id] = st[d + dep[now]].size();
        else ans[id] = 0;
    }
    if(keep == 0)
    {
        for(int i=L[now]; i<=R[now]; i++)
            st[dep[rnk[i]]].clear();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> s[i] >> fa[i];
        if(fa[i])
            gra[fa[i]].push_back(i);
    }
    for(int i=1; i<=n; i++)
        if(fa[i] == 0) dfs1(i, 0);
    cin >> m;
    for(int i=0; i<m; i++)
    {
        int a, b;
        cin >> a >> b;
        qs[a].push_back({b, i});
    }
    for(int i=1; i<=n; i++)
        if(fa[i] == 0) dfs2(i, 0);
    for(int i=0; i<m; i++)
        cout << ans[i] << "\n";
    return 0;
}