虽然这题是一道二合一,也不算难,但还是学到了很多东西啊,\(k\) 级儿子个数的五种求法!!我还是觉得四种比较好(
首先 \(k\) 级祖先很好求,离线的话dfs的时候开个栈就好了。长链剖分也可以但我不会,倍增什么的就不用说了。
就是求一个子树里为某一个深度的点的个数嘛,这个明显可以dsu on tree啊,开个桶记录下各种深度的有几个就好了。
复杂度:\(O(nlogn)\)
转化为dfs序,就是一个区间里等于某一个数的个数,离线+树状数组。
复杂度:\(O(nlogn)\)
给每个深度开一个vector,里面按照dfs序把点排好,询问时只要二分出区间左右端点就好了。
这个做法虽然也是 \(O(nlogn)\) ,但它是在线的,很妙啊!!
这个是模板了吧,用一个简单的DP统计一下就好了
复杂度 \(O(n)\)
#include<bits/stdc++.h>
#define ll long long
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=1000003;
const int M=N<<1;
int n,q;
int cnt,head[N],Next[M],v[M];
vector<int> id[N];
int qk[N];
void read(int &x){
char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
}
void add(int x,int y){
Next[++cnt]=head[x];
head[x]=cnt;
v[cnt]=y;
}
int st[N],L;
int d[N],bc[N],ls[N],*f[N],*now=ls;
//vector<int> qry[N];
void predfs(int x,int fa,int dep){
st[dep]=x;
//int bc=0;
for(auto tmp:id[x])
if (dep>qk[tmp])
id[st[dep-qk[tmp]]].push_back(tmp);
id[x].resize(0);
for(int i=head[x];i;i=Next[i]){
predfs(v[i],x,dep+1);
if (d[v[i]]>d[bc[x]]) bc[x]=v[i];
}
d[x]=d[bc[x]]+1;
}
int ans[N];
void dfs(int x,int fa){
f[x][0]=1;
if (bc[x]) f[bc[x]]=f[x]+1,dfs(bc[x],x);
for(int i=head[x];i;i=Next[i]){
int tmp=v[i];
if (tmp==bc[x]) continue;
f[tmp]=now;now+=d[tmp];
dfs(tmp,x);
fr(j,1,d[tmp]) f[x][j]+=f[tmp][j-1];
}
for(auto tmp:id[x])
ans[tmp]=f[x][qk[tmp]]-1;
}
int main(){
read(n);read(q);
int x;
fr(i,2,n){
read(x);
add(x,i);
}
fr(i,1,q){
read(x);read(qk[i]);
id[x].push_back(i);
}
predfs(1,0,1);
f[1]=now;now+=d[1];
fr(i,1,n) for(auto j:id[i]) printf("%d ",j);puts("---");
dfs(1,0);
fr(i,1,q) printf("%d ",qk[i]==0?0:ans[i]);
return 0;
}
这是标算,,想不到……
我们dfs的时候记录一个 \(cnt_i\) 表示dfs过的里面深度为 \(i\) 的有多少个,然后求一个子树里深度为 \(d\) 的个数只要把dfs这个子树前后的 \(cnt_d\) 减一减就好了。
原文:https://www.cnblogs.com/ymzqwq/p/11809162.html