5776. 【NOIP2008模拟】小x游世界树

Description

小x得到了一个(不可靠的)小道消息，传说中的神岛阿瓦隆在格陵兰海的某处,据说那里埋藏着亚瑟王的宝藏，这引起了小x的好奇，但当他想前往阿瓦隆时发现那里只有圣诞节时才能到达，然而现在已经春天了，不甘心的他将自己的目的地改成了世界树，他耗费了大量的时间，终于将自己传送到了世界树下。世界树是一棵非常巨大的树，它有着许许多多的枝条以及节点，每个节点上都有一个平台。好不容易来到传说中的世界树下，小x当然要爬上去看看风景。小x每经过一条边都会耗费体力值。然而世界树之主想给他弄（gáo）些（dǐan）麻（shì）烦（qíng），于是他在每条边上都设了一个魔法阵，当小x踏上那条边时会被传送回根节点，魔法阵只生效一次。这岂不是要累死小x？幸运的是，每个平台上都有无数个加速器，这些加速器可以让小x在当前节点所连的边上耗费的体力值减少，不同平台的加速器性能不一定相同，但同一个平台的加速器性能绝对相同。世界树之主给了小x一次“换根”的机会，他可以将世界树的任何一个节点变为根，但所有的边都不能改变。小x想问你，将根换为哪个节点能使小x爬到世界树上的每个节点耗费的体力值和最少。默认编号为1的点为初始根。

Input

　　第一行一个数n，表示有n个节点。
　　第二行n个数ai，表示每个平台上的加速器的性能。
　　第三至n+1行，每行三个数bi,ci,di分别表示这条无向边的起点，终点与耗费的能量值。

Output

第一行一个数，表示要换成的节点，如果有多个点为根时耗费的体力值都最小，则输出编号最小的那个。如果保持为1是最优的，就输出1。
第二行一个数，表示最小耗费的体力值。

Solutions

其实并不是每个点都要建一次树，我们可以在一个点为整棵树的根节点时，以它的答案来更新它的儿子节点的答案。

如果将根节点的儿子换为根，会变动的只有根节点与被换的那个儿子之间的边。

代码

 1 var
 2   min:int64;
 3   n,nm,root:longint;
 4   a,v,f:array [0..700001] of longint;
 5   fa,ans:array [0..700001] of int64;
 6   ls,y,w,next:array [0..1400001] of longint;
 7 procedure add(o,p,q:longint);
 8 begin
 9   inc(nm);
10   y[nm]:=p; w[nm]:=q; next[nm]:=ls[o];
11   ls[o]:=nm;
12 end;
13 
14 procedure init;
15 var
16   i,o,p,q:longint;
17 begin
18   fillchar(fa,sizeof(fa),0);
19   fillchar(v,sizeof(v),0);
20   fillchar(f,sizeof(f),0);
21   fillchar(ans,sizeof(ans),0);
22   readln(n);
23   for i:=1 to n do
24     read(a[i]);
25   nm:=0;
26   for i:=1 to n-1 do
27     begin
28       readln(o,p,q);
29       add(o,p,q);
30       add(p,o,q);
31     end;
32 end;
33 
34 procedure dfs(x:longint);
35 var
36   i:longint;
37 begin
38   if v[x]=1 then exit;
39   v[x]:=1; i:=ls[x];
40   while i<>0 do
41     begin
42       if v[y[i]]=0 then
43         begin
44           f[y[i]]:=f[x]+w[i]-a[x];
45           ans[1]:=ans[1]+f[y[i]];
46           dfs(y[i]);
47           fa[x]:=fa[x]+fa[y[i]]+1;
48         end;
49       i:=next[i];
50     end;
51 end;
52 
53 procedure main(x:longint);
54 var
55   i,t,k:longint;
56 begin
57   if v[x]=1 then exit;
58   v[x]:=1; i:=ls[x];
59   while i<>0 do
60     begin
61       if v[y[i]]=0 then
62         begin
63           ans[y[i]]:=ans[x]-(fa[y[i]]+1)*(w[i]-a[x])+(fa[x]-fa[y[i]])*(w[i]-a[y[i]]);
64           if (ans[y[i]]<min) or (y[i]<root) and (min=ans[y[i]]) then
65             begin
66               root:=y[i]; min:=ans[y[i]];
67             end;
68           t:=fa[x]; fa[x]:=fa[x]-fa[y[i]]-1;
69           k:=fa[y[i]]; fa[y[i]]:=t;
70           main(y[i]);
71           fa[x]:=t; fa[y[i]]:=k;
72         end;
73       i:=next[i];
74     end;
75 end;
76 
77 begin
78   assign(input,'yggdrasil.in');
79   assign(output,'yggdrasil.out');
80   reset(input);
81   rewrite(output);
82   init;
83   dfs(1);
84   fillchar(v,sizeof(v),0);
85   root:=1; min:=ans[1];
86   main(1);
87   writeln(root);
88   writeln(min);
89   close(input);
90   close(output);
91 end.