首页 > 代码库 > 1131: [POI2008]Sta

1131: [POI2008]Sta

2024-11-25 05:26:01   204人阅读

1131: [POI2008]Sta

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 783  Solved: 235
[Submit][Status]

Description

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

Input

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

Output

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

Sample Input

8
1 4
5 6
4 5
6 7
6 8
2 4
3 4

Sample Output

7

HINT

 

Source

 

题解：一道萌萌哒树状DP，先是随便弄一个点然后建树，求出各点的深度，然后求和，然后在这个你建立的有根树上各个分支进行DP，以各个点为根时的深度并不难维护——设当前总和为X，你想转移到的子节点下属共计Y个节点（算自己），整个树N个节点，那么这次转移后的总和为X-Y+(N-Y)，别的没了。。。对于P党小心202（爆栈！！！）
 1 {$M 10000000,0,maxlongint} 2 type 3     point=^node; 4     node=record 5                g:longint; 6                next:point; 7     end; 8   9 var10    i,j,k,l,m,n:longint;11    a1,a2:int64;12    a:array[0..2000000] of point;13    b,c,d,e:array[0..2000000] of int64;14 procedure add(x,y:longint);inline;15           var p:point;16           begin17                if x=y then exit;18                new(p);19                p^.g:=y;20                p^.next:=a[x];21                a[x]:=p;22           end;23 procedure built(x:longint);inline;24           var p:point;25           begin26                p:=a[x];27                c[x]:=1;28                while p<>nil do29                      begin30                           if d[p^.g]=0 then31                              begin32                                   d[p^.g]:=1;33                                   b[p^.g]:=b[x]+1;34                                   built(p^.g);35                                   c[x]:=c[x]+c[p^.g];36                              end;37                           p:=p^.next;38                      end;39           end;40 procedure run(x:longint);inline;41           var p:point;42           begin43                p:=a[x];44                while p<>nil do45                      begin46                           if d[p^.g]=0 then47                              begin48                                   d[p^.g]:=1;49                                   e[p^.g]:=e[x]+int64(n)-(2*c[p^.g]);50                                   run(p^.g);51                              end;52                           p:=p^.next;53                      end;54           end;55  56 begin57      readln(n);58      for i:=1 to n do a[i]:=nil;59      for i:=1 to n-1 do60          begin61               readln(j,k);62               add(j,k);add(k,j);63          end;64      fillchar(b,sizeof(b),0);65      fillchar(c,sizeof(c),0);66      fillchar(d,sizeof(d),0);67      d[1]:=1;68      built(1);69      fillchar(d,sizeof(d),0);70      fillchar(e,sizeof(e),0);71      d[1]:=1;72      for i:=1 to n do e[1]:=e[1]+b[i];73      run(1);74      a1:=-1;a2:=0;75      for i:=1 to n do76          begin77               if e[i]>a1 then78                  begin79                       a1:=e[i];80                       a2:=i;81                  end;82          end;83      writeln(a2);84      readln;85 end.

 

1131: [POI2008]Sta


联系
我们