CF246E Blood Cousins Return 题解

· · 题解

前言

感谢 @zhengdongwen 大佬给予我的非常关键的帮助（拜谢）。

分析

考虑莫队。

对于这道题，我们可以想到 DFS 序。定义 \mathit{siz}_{i} 表示在以 i 为根的子树中的节点数量。若有节点 x 在 DFS 序的位置为 \mathit{where}_{x}，则其子树中的节点将会完全分布在 \mathit{where}_{x} 到 \mathit{where}_{x}+\mathit{siz}_{x}-1 中。这样，对于一个问题：求以 x 为根的子树中深度比 x 大 y 的所有节点不同名字的数量。就变成了：在 DFS 序中，求区间 [\mathit{where}_{x},\mathit{where}_{x}+\mathit{siz}_{x}-1] 里所有对应节点的深度比 x 大 y 的不同名字数量。

这是一个区间问题，直接用莫队维护。定义 \mathit{cnt}_{i,j} 表示在当前指针范围内，深度为 i，名字为 j 的节点数量。和 P1972 相同，统计一下每一个深度的名字不同数量，记为 \mathit{many}_{i}。则答案就是 \mathit{many}_{depth_x+y}。

注：我们需要使用类似于 map 的容器存放 \mathit{cnt}_{i,j}，以确保不会 MLE。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define x first
#define y second
#define re register
#define il inline 
const int N=1e6+10;
int n,q;
string name[N];

//dfs序 ↓ 
int ne[N],e[N],h[N],idx;
int fi[N],dfsx[N],cnt,dep[N];//fi[i]：节点i在dfs序中出现的下标 
int siz[N];
il void add(int a,int b){
    ne[++idx]=h[a],e[idx]=b,h[a]=idx;
    return ;
}
il void dfs(int now,int fa){
    dep[now]=dep[fa]+1,dfsx[++cnt]=now,fi[now]=cnt;
    siz[now]=1;
    for(int i=h[now];i;i=ne[i]){
        int j=e[i];if(j==fa) continue;
        dfs(j,now),siz[now]+=siz[j];
    }
    return ;
}
//dfs序 ↑ 

//输入 ↓
struct node{
    int l,r,dep,id;//dep存放dep[x]+y 
}Q[N];
il void read(){ 
    scanf("%lld",&n); 
    int idex=0;
    for(int i=1;i<=n;i++){ 
        int x; cin>>name[i];scanf("%lld",&x);
        add(x,i),add(i,x);
    }
    dfs(0,-1); scanf("%lld",&q); 
    for(int i=1;i<=q;i++){
        int x,y;scanf("%lld%lld",&x,&y);
        Q[i]={fi[x],fi[x]+siz[x]-1,dep[x]+y,i};
    }
    return ;    
}
//输入 ↑ 

//莫队 ↓ 
int len,ANS[N];
int many[N];
unordered_map<int,unordered_map<string,int>> h_m;
bool cmp(node a,node b){
    if(a.l/len!=b.l/len) return a.l<b.l;
    if((a.l/len)&1) return a.r<b.r;
    return a.r>b.r;
}
void add1(int x){
    h_m[dep[x]][name[x]]++;
    if(h_m[dep[x]][name[x]]==1) 
        many[dep[x]]++;
    return ;
}
void del1(int x){
    h_m[dep[x]][name[x]]--;
    if(h_m[dep[x]][name[x]]==0)
        many[dep[x]]--;
    return ;
}
void solve(){
    len=sqrt(n),sort(Q+1,Q+q+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=q;i++){
        while(l>Q[i].l) add1(dfsx[--l]);
        while(r<Q[i].r) add1(dfsx[++r]);
        while(l<Q[i].l) del1(dfsx[l++]);
        while(r>Q[i].r) del1(dfsx[r--]);
        ANS[Q[i].id]=many[Q[i].dep];
    }
    return ;
}
//莫队 ↑ 

void print(){
    for(int i=1;i<=q;i++)
        printf("%lld\n",ANS[i]); 
    return ;
}
signed main(){
    read(),solve(),print();return 0;
}