bzoj 1131 [POI2008]Sta 树形dp 转移根模板题-白红宇

bzoj 1131 [POI2008]Sta 树形dp 转移根模板题

阅读量：4580 次

发布时间：2019-06-09

本文共 1514 字，大约阅读时间需要 5 分钟。

[POI2008]Sta

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 1889 Solved: 729

[][][]

Description

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大

Input

给出一个数字N,代表有N个点.N<=1000000 下面N-1条边.

Output

输出你所找到的点,如果具有多个解,请输出编号最小的那个.

Sample Input

1 4

5 6

4 5

6 7

6 8

2 4

3 4

Sample Output

HINT

题解：这是一道裸题

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 9 #define N 100000710 #define ll long long11 using namespace std;12 inline int read()13 {14 int x=0,f=1;char ch=getchar();15 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();}16 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}17 return x*f;18 }19 20 int n,m,id;21 int cnt,hed[N],rea[N<<1],nxt[N<<1];22 ll sum[N],dep[N],siz[N];23 24 void add(int u,int v)25 {26 nxt[++cnt]=hed[u];27 hed[u]=cnt;28 rea[cnt]=v;29 }30 void add_two_way(int x,int y)31 {32 add(x,y);33 add(y,x);34 }35 void dfs1(int u,int fa)36 {37 siz[u]=1;38 for (int i=hed[u];i!=-1;i=nxt[i])39 {40 int v=rea[i];41 if (v==fa) continue;42 dep[v]=dep[u]+1;43 dfs1(v,u);44 sum[u]+=sum[v],siz[u]+=siz[v];45 }46 sum[u]+=dep[u];47 }48 void dfs2(int u,int fa)49 {50 for (int i=hed[u];~i;i=nxt[i])51 {52 int v=rea[i];53 if (v==fa) continue;54 sum[v]=sum[u]-siz[v]+n-siz[v];55 dfs2(v,u);56 }57 }58 int main()59 {60 memset(hed,-1,sizeof(hed));61 n=read();62 for (int i=1;i
            
             sum[id]) id=i;66 printf("%d\n",id);67 }