启发式合并(树上)

一般用于: 查询每一个子树的相关所有信息, 

内容:

• 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]<<" ";
    

}