Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 783 Solved: 235
给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
给出一个数字N,代表有N个点.N<=1000000 下面N-1条边.
输出你所找到的点,如果具有多个解,请输出编号最小的那个.
8 1 4 5 6 4 5 6 7 6 8 2 4 3 4
7
题解:一道萌萌哒树状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 var
10 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 begin
17 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 begin
26 p:=a[x];
27 c[x]:=1;
28 while p<>nil do
29 begin
30 if d[p^.g]=0 then
31 begin
32 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 begin
43 p:=a[x];
44 while p<>nil do
45 begin
46 if d[p^.g]=0 then
47 begin
48 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 begin
57 readln(n);
58 for i:=1 to n do a[i]:=nil;
59 for i:=1 to n-1 do
60 begin
61 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 do
76 begin
77 if e[i]>a1 then
78 begin
79 a1:=e[i];
80 a2:=i;
81 end;
82 end;
83 writeln(a2);
84 readln;
85 end.