首页 > 其他 > 详细

树链剖分 探究

时间:2018-01-14 16:32:41      阅读:20      评论:0      收藏:0      [点我收藏+]

标签:tin   mar   return   urn   init   for   its   -m   const   

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+11;
int sz[maxn],dep[maxn],top[maxn],fa[maxn],son[maxn],dfn[maxn],pre[maxn];
//pre = ~ dfn
int to[maxn<<1],nxt[maxn<<1],head[maxn],tot,tot2;
void init(){memset(head,-1,sizeof head); tot=tot2=0;}
void add(int u,int v){
    to[tot]=v;nxt[tot]=head[u];head[u]=tot++;
    swap(u,v);
    to[tot]=v;nxt[tot]=head[u];head[u]=tot++;
}
void dfs1(int u,int p,int d){//sz fa son dep
    fa[u]=p;sz[u]=1;dep[u]=d;
    for(int i = head[u]; ~i; i = nxt[i]){
        int v=to[i];
        if(v==p)continue;
        dfs1(v,u,d+1);
        sz[u]+=sz[v]; //note
        if(!son[u]) son[u]=v;
        else if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int tp){ //dfn pre | top
    pre[++tot2]=u;
    dfn[u]=tot2;
    top[u]=tp;
    if(son[u]) dfs2(son[u],tp); //只要有edge
    for(int i = head[u]; ~i; i = nxt[i]){
        int v=to[i];
        if(v==fa[u]||v==son[u]) continue;//not fa | hson
        dfs2(v,v);
    }
}
int main(){
    int u,v;
    init();
    while(cin>>u>>v){
        add(u,v);
        if(u==-1){
            dfs1(1,0,1);
            dfs2(1,1);
            cout<<tot2<<endl;
            for(int i = 1; i <= tot2; i++){
                cout<<i<<" "<<"sz "<<sz[i]<<" son "<<son[i]
                    <<" top "<<top[i]<<" dfn "<<dfn[i]<<" pre"
                    <<pre[i]<<endl;
            }
            for(int i = 1; i <= tot2; i++) cout<<(dfn[pre[i]]==i)<<endl;
            break;
        }
    }
    return 0;
}

Input
1 2
1 4
2 5
2 6
1 3
4 8
4 9
4 10
6 11
6 12
3 7
9 13
13 14
-1 -1

Output
14
1 sz 14 son 4 top 1 dfn 1 pre1
2 sz 5 son 6 top 2 dfn 10 pre4
3 sz 2 son 7 top 3 dfn 8 pre9
4 sz 6 son 9 top 1 dfn 2 pre13
5 sz 1 son 0 top 5 dfn 14 pre14
6 sz 3 son 12 top 2 dfn 11 pre10
7 sz 1 son 0 top 3 dfn 9 pre8
8 sz 1 son 0 top 8 dfn 7 pre3
9 sz 3 son 13 top 1 dfn 3 pre7
10 sz 1 son 0 top 10 dfn 6 pre2
11 sz 1 son 0 top 11 dfn 13 pre6
12 sz 1 son 0 top 2 dfn 12 pre12
13 sz 2 son 14 top 1 dfn 4 pre11
14 sz 1 son 0 top 1 dfn 5 pre5
1
1
1
1
1
1
1
1
1
1
1
1
1
1

树链剖分 探究

标签:tin   mar   return   urn   init   for   its   -m   const   

原文:https://www.cnblogs.com/caturra/p/8283527.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号