一般用于: 查询每一个子树的相关所有信息,
内容:
- dfs,后, 合并儿子的时候, 继承一个重儿子, 然后把其他儿子暴力合进去就行了, 最坏的时间复杂度: Nlong N
- 如何继承的时候不是暴力捏? 给 每一个点赋值一个新的ID,就行了.
- 重点是在结构体 tr[] 节点里面的各种定义的东西, 来实现我这个代码啥的, 要写相关的函数的(面向对象编程,(和项目比较像了)
- map,vector 啥的, 动态内存去存.
例题:
- 找到那个深度的父亲利用二进制优化即可
#include <bits/stdc++.h> using namespace std; #define ri int #define M 200005 int n,m; int T; vector <int> p[M]; int vis[M]; int fa[M][32]; void dfs1(int a) { vis[a]=1; for(ri i=1;i<=30;i++) fa[a][i]=fa[fa[a][i-1]][i-1]; for(ri b:p[a]) { if(vis[b]) continue; dfs1(b); } } struct tt{ int id; int val; }; vector <tt> qu[M]; int son[M],dep[M]; struct node{ map<int,int>num; vector<int>lt; void add(int a) { num[dep[a]]++; lt.push_back(a); } }tr[M]; int sz[M]; int ans[M]; int id[M]; int cur=0; void dfs2(int a,int f) { id[a]=++cur; dep[a]=dep[f]+1; vis[a]=1; int mx=0; for(ri b:p[a]) { if(vis[b]) continue; dfs2(b,a); if(sz[b]>mx) { mx=sz[b]; son[a]=b; } sz[a]+=sz[b]; } if(son[a]) id[a]=id[son[a]]; for(ri b:p[a]) { if(b==f||b==son[a]) continue; for(ri v:tr[id[b]].lt) tr[id[a]].add(v); } for(tt t:qu[a]) { ans[t.id]=max(tr[id[a]].num[dep[a]+t.val]-1,0); } tr[id[a]].add(a); sz[a]++; } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n; for(ri i=1;i<=n;i++) { int a; cin>>a; fa[i][0]=a; if(a==0) { continue; } p[a].push_back(i); } for(ri i=1;i<=n;i++) { if(fa[i][0]==0) { dfs1(i); } } cin>>m; for(ri i=1;i<=m;i++) { int a,b; cin>>a>>b; tt t; t.id=i; t.val=b; int cnt=0; while(b) { if(b&1) a=fa[a][cnt]; b>>=1;cnt++; } if(a) { qu[a].push_back(t); } } memset(vis,0,sizeof(vis)); for(ri i=1;i<=n;i++) { if(fa[i][0]==0) { dfs2(i,0); } } for(ri i=1;i<=m;i++) cout<<ans[i]<<" "; }