Blood Cousins Return

板子题...并没有太多的变化.和之前做的,唯一的变化就是对于字符串可以哈希成数字的变成点权.
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
//可以用map把每个字符串做一次离散化,这样就相当于查询权值了.
map<string,int>mp;
vector<int>v[N<<1];
int w[N];//存这个点的权值.
int dfn[N],Son,sz[N];
int dep[N];
set<int>s[N<<1];
struct Ans{
    int k,id,res;
};
vector<Ans>cnt[N];
int ans[N];

void dfs(int u,int fa)
{
    sz[u]=1;dep[u]+=dep[fa]+1;
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa) continue;
        dfs(son,u);sz[u]+=sz[son];
        if(sz[son]>sz[dfn[u]])  dfn[u]=son;
    }
}

void cal(int u,int fa,bool op)
{
    if(op)  s[dep[u]].insert(w[u]);
    else    s[dep[u]].clear();
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa||son==Son)   continue;
        cal(son,u,op);
    }
}

void dfs(int u,int fa,bool op)
{
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==dfn[u]||son==fa)    continue;
        dfs(son,u,true);
    }
    if(dfn[u])  dfs(dfn[u],u,false),Son=dfn[u];
    cal(u,fa,true);
    for(int i=0;i<(int)cnt[u].size();i++)
    {
        int Dep=dep[u]+cnt[u][i].k;
        cnt[u][i].res=s[Dep].size();
    }
    Son=0;
    if(op)
    {
        cal(u,fa,false);
    }
}

int main()
{
    int n,mk=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        string a;int u;
        cin>>a>>u;
        if(!mp[a])   mp[a]=++mk;
        w[i]=mp[a];
        v[i].push_back(u);
        v[u].push_back(i);
    }//处理权值.
    dfs(0,0);
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int u,Dep;
        scanf("%d%d",&u,&Dep);
        cnt[u].push_back({Dep,i,0});
    }
    dfs(0,0,true);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(int)cnt[i].size();j++)
        {
            ans[cnt[i][j].id]=cnt[i][j].res;
        }
    }
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}

还有一题就不写专心写题了,学线代汇编物理马原之类的去了,随便去上课~