这题有紫??
对于询问节点 \(u\),倍增地跳到它的 \(k\) 级祖先,求其子树内有多少深度为 \(dep_u\) 的节点。
我们考虑把询问离线,再通过 dfs 序把树拍平,然后扫一遍直接求就行了。
复杂度 \(O(n\log n)\)。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,q,ans[N],l[N],r[N],tot=0,a[N],dep[N],fa[N][22],cnt[N];
vector<int>adj[N];
struct node{
int val,id,op;
node(int val=0,int id=0,int op=0):val(val),id(id),op(op){}
};
vector<node>d[N];
void dfs(int u,int lst){
l[u]=++tot;dep[u]=dep[lst]+1;a[tot]=dep[u];
for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=0;i<adj[u].size();++i)dfs(adj[u][i],u);
r[u]=tot;
}
int main(){
cin>>n>>q;
for(int i=2;i<=n;++i){
fa[i][0]=read();
adj[fa[i][0]].push_back(i);
}
dfs(1,0);
for(int i=1;i<=q;++i){
int u,t,v;u=read();t=read();v=dep[u];
for(int i=0;i<=20;++i)if((t>>i)&1)u=fa[u][i];
d[l[u]-1].push_back(node(v,i,-1));
d[r[u]].push_back(node(v,i,1));
}
for(int i=1;i<=n;++i){
++cnt[a[i]];
for(int j=0;j<d[i].size();++j){
node tmp=d[i][j];
ans[tmp.id]+=tmp.op*cnt[tmp.val];
}
}
for(int i=1;i<=q;++i)printf("%d ",max(ans[i]-1,0));
cout<<endl;
return 0;
}
标签:node,ch,val,int,题解,dep,P5384,id
From: https://www.cnblogs.com/HQJ2007/p/17561374.html