# 树链剖分 探究

``````#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
swap(u,v);
}
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){
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

(0)
(0)

0条