【dfs序+二分】ABC202 E Count Descendants

你的名字 2024-03-16 14:04 2阅读 0赞

[E - Count Descendants (atcoder.jp)][E - Count Descendants _atcoder.jp]

题意：

![658e3c961b5b49af878533726aa54474.png][]

![07c62dbd1a584b8989c13fb18d064dda.png][]

思路：

一开始的想法是，树形DP预处理出在子树u中，离结点u距离为j的结点个数，然后直接输出答案

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int N,Q,u,d;
    int tot=0;
    int p[mxn];
    int head[mxn],dep[mxn],dp[mxn][100];
    
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void dfs1(int u,int fa){
    	dep[u]=dep[fa]+1;
    	dp[u][0]=1;
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs1(edge[i].to,u);
    	}
    }
    void dfs2(int u,int fa){
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs2(edge[i].to,u);
    		for(int j=1;j<=100;j++){
    			dp[u][j]+=dp[edge[i].to][j-1];
    		}
    	}
    }
    void solve(){
    	cin>>N;
    	G_init();
    	for(int i=2;i<=N;i++) cin>>p[i];
    	for(int i=2;i<=N;i++){
    		add(i,p[i]);
    		add(p[i],i);
    	}
    	dfs1(1,0);
    	for(int i=1;i<=N;i++) dep[i]--;
    	dfs2(1,0);
    	cin>>Q;
    	for(int i=1;i<=Q;i++){
    		cin>>u>>d;
    		if(dep[u]>d) cout<<0<<'\n';
    		else{
    			int delta=d-dep[u];
    			cout<<dp[u][delta]<<'\n';
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

显然，题目没有说它是一棵二叉树，因此树高不止100，不能用树形DP预处理

正解是dfs序

先预处理出每个结点的入序和出序，对于每一次询问，查询在深度d的所有结点中dfs序在\[In\[u\],Out\[u\]\]之间的结点个数即可，所以我们需要预处理出对于每个深度，这个深度的所有结点的dfs序，把它们放进vector就好了

**当我们要在子树中找点时，考虑在dfs序中这个序列里面某个区间里面找点**

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    vector<int> V[mxn];
    
    int N,Q,u,d;
    int tot=0,idx=0;
    int head[mxn];
    int p[mxn],In[mxn],Out[mxn],dep[mxn];
    
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void dfs(int u,int fa){
    	dep[u]=dep[fa]+1;
    	In[u]=++idx;
    	V[dep[u]].push_back(In[u]);
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		dfs(edge[i].to,u);
    	}
    	Out[u]=++idx;
    }
    void solve(){
    	cin>>N;
    	G_init();
    	for(int i=2;i<=N;i++) cin>>p[i];
    	for(int i=2;i<=N;i++){
    		add(i,p[i]);
    		add(p[i],i);
    	}
    	dfs(1,0);
    	cin>>Q;
    	for(int i=1;i<=Q;i++){
    		cin>>u>>d;
    		d++;
    		cout<<lower_bound(V[d].begin(),V[d].end(),Out[u])-lower_bound(V[d].begin(),V[d].end(),In[u])<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[E - Count Descendants _atcoder.jp]: https://atcoder.jp/contests/abc202/tasks/abc202_e
[658e3c961b5b49af878533726aa54474.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/d2304618ca3e49ac8f2d779630053c71.png
[07c62dbd1a584b8989c13fb18d064dda.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/4c65adccbe364a1991c1754b86427fde.png