题解 CF246E 【Blood Cousins Return】

(quad)题目链接：CF246E Blood Cousins Return(洛谷的链接)

(quad)一道 (Dcu) 模板题(下面会讲)，只需要用一个 (map) 数组来维护这个名字(字符串)是否出现过，用 (set) 也可以，貌似会慢一些，用 (cnt) 数组来维护每一层的不同名字的数量即可，因为是一个森林，所以记得要清空数组。

一个大坑点：

(quad) (WA)第 (50) 个点的注意了，在储存询问时一定要判断询问这个第 (k) 级儿子的深度是否超过了 (10^5) ，因为最多只有 (10^5) 个点，如果超过就不用存储，答案一定是 (0) ，存储的话会溢出数组，遇到一些毒瘤数据就会WA。

(quad)下面就简单讲讲树上启发式合并 ((DSU) (on) (Tree))算法，如果有不懂的可以提出来。

(quad)学这个之前需要对树上操作、 (dfs) 序和轻重链剖分等知识有一定了解，最好已经掌握了树链剖分。

(quad)树上启发式合并 ((DSU) (on) (Tree))，是一个在 (O(nlogn)) 时间内解决许多树上问题的有力算法，对于某些树上离线问题可以速度大于等于大部分算法且更易于理解和实现。

(quad)先想一下暴力算法，对于每一次询问都遍历整棵子树，然后统计答案，最后再清空cnt数组，最坏情况是时间复杂度为 (O(n^2)) ，对于 (10^5) 的数据肯定是过不去的。

(quad)现在考虑优化算法，暴力算法跑得慢的原因就是多次遍历，多次清空数组，一个显然的优化就是将询问同一个子树的询问放在一起处理，但这样还是没有处理到关键，最坏情况时间复杂度还是 (O(n^2)) ，考虑到询问 (x) 节点时， (x) 的子树对答案有贡献，所以可以不用清空数组，先统计 (x) 的子树中的答案，再统计 (x) 的答案，这样就需要提前处理好 (dfs) 序。

(quad)然后我们可以考虑一个优化，遍历到最后一个子树时是不用清空的，因为它不会产生对其他节点影响了，根据贪心的思想我们当然要把节点数最多的子树（即重儿子形成的子树）放在最后，之后我们就有了一个看似比较快的算法，先遍历所有的轻儿子节点形成的子树，统计答案但是不保留数据，然后遍历重儿子，统计答案并且保留数据，最后再遍历轻儿子以及父节点，合并重儿子统计过的答案。

(quad)其实树上启发式合并的基本思路就是这样，可以看一下代码理解。

il int check(int x)//统计答案
{
  int num=0,ret=0;
  for(re i=1;i<=n;i++)
    {
      if(cnt[i]==num){ret+=i;}
      else if(cnt[i]>num){num=cnt[i],ret=i;}
    }
  return ret;
}
il void add(int x){cnt[col[x]]++;}//单点增加
il void del(int x){cnt[col[x]]--;}//单点减少
il void raise(int x){for(re i=seg[x];i<=seg[x]+size[x]-1;i++)add(rev[i]);}//增加x子树的贡献
il void clear(int x){for(re i=seg[x];i<=seg[x]+size[x]-1;i++)del(rev[i]);}//清空x子树的贡献
il void dfs1(int x,int fa)
{
  dep[x]=dep[fa]+1;father[x]=fa;//处理深度，父亲
  seg[x]=++seg[0];rev[seg[x]]=x;size[x]=1;//子树大小，dfs序
  for(re i=head[x],y;i,y=go[i];i=next[i])
    {
      if(y==fa)continue;dfs1(y,x);
      size[x]+=size[y];
      if(size[y]>size[son[x]])son[x]=y;//重儿子
    }
}
il void dfs2(int x,int flag)//flag表示是否为重儿子，1表示重儿子，0表示轻儿子
{
  for(re i=head[x],y;i,y=go[i];i=next[i])
    {
      if(y==son[x]||y==father[x])continue;
      dfs2(y,0);//先遍历轻儿子
    }
  if(son[x])dfs2(son[x],1);//再遍历重儿子
  for(re i=head[x],y;i,y=go[i];i=next[i])
    {
      if(y==son[x]||y==father[x])continue;
      raise(y);//更新轻儿子的贡献
    }add(x);//加上x结点本身的贡献
  ans[x]=check(x);//更新答案
  if(!flag)clear(x);//如果是轻儿子，就清空
}

(quad)上面的只是模板的代码，此题的完整代码在下面。(附带注释)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
#define re register int
#define int long long
#define LL long long
#define il inline
#define next nee
#define inf 1e18
il int read()
{
  int x=0,f=1;char ch=getchar();
  while(!isdigit(ch)&&ch!='-')ch=getchar();
  if(ch=='-')f=-1,ch=getchar();
  while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
  return x*f;
}
il void print(int x)
{
  if(x<0)putchar('-'),x=-x;
  if(x/10)print(x/10);
  putchar(x%10+'0');
}
const int N=1e5+5;
int n,m,next[N],go[N],head[N],tot,father[N],ans[N];
int dep[N],son[N],seg[N],rev[N],size[N],cnt[N];
struct node{int k,id;};
string s[N]; 
vector<node>q[N];
map<string,bool>c[N];

il void Add(int x,int y)
{
  next[++tot]=head[x];
  head[x]=tot;go[tot]=y;
}
il void add(int x)//单点增加
{
  if(!c[dep[x]][s[x]])c[dep[x]][s[x]]=1,cnt[dep[x]]++;
}
il void raise(int x)//算上x子树的贡献
{
  for(re i=seg[x];i<=seg[x]+size[x]-1;i++)add(rev[i]);
}
il void del(int x)//单点减少
{
  c[dep[x]].clear();
  cnt[dep[x]]=0;
}
il void clear(int x)//清空x子树
{
  for(re i=seg[x];i<=seg[x]+size[x]-1;i++)
    del(rev[i]);
}
il void dfs1(int x,int fa)
{
  dep[x]=dep[fa]+1;size[x]=1;seg[x]=++seg[0];rev[seg[x]]=x;
  for(re i=head[x],y;i,y=go[i];i=next[i])
    {
      dfs1(y,x);size[x]+=size[y];
      if(size[y]>size[son[x]])son[x]=y;
    }
}
il void dfs2(int x,int flag)
{
  for(re i=head[x],y;i,y=go[i];i=next[i])
    {
      if(y==son[x])continue;
      dfs2(y,0);//先遍历轻儿子
    }
  if(son[x])dfs2(son[x],1);//再遍历重儿子
  for(re i=head[x],y;i,y=go[i];i=next[i])
    {if(y==son[x])continue;raise(y);}//更新轻儿子的贡献
  add(x);//加上x结点本身的贡献
  for(re i=0;i<q[x].size();i++)
    ans[q[x][i].id]=cnt[dep[x]+q[x][i].k];//更新答案
  if(!flag)clear(x);//如果是轻儿子，就清空
}
signed main()
{
  n=read();
  for(re i=1,x;i<=n;i++)cin>>s[i],x=read(),father[i]=x,Add(x,i);
  for(re i=1;i<=n;i++)if(!father[i])dfs1(i,0);//预处理，倍增数组、dfs序等树上信息,记得要用循环，从每棵树的根节点出发
  m=read();
  for(re i=1,x,y;i<=m;i++)
    {
      x=read(),y=read();
      if(dep[x]+y>=N)continue;//注意，如果询问的第K级儿子超过限制，不能存储，原因上面有
      q[x].push_back((node){y,i});
    }
  for(re i=1;i<=n;i++)if(!father[i])dfs2(i,0);//找每棵树的根节点，0表示轻儿子，这样不用手动清空数组
  for(re i=1;i<=m;i++)print(ans[i]),putchar('
');
  return 0;
}