5776. 【NOIP2008模擬】小x游世界樹?
(File IO):?input:yggdrasil.in?output:yggdrasil.out

Time Limits:?1500 ms??Memory Limits:?262144 KB??Detailed Limits?? Goto ProblemSet

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。
? ? ? ? ?第二行一個數，表示最小耗費的體力值。

Sample Input

4 2 1 3 3 1 2 3 1 3 4 2 4 6

Sample Output

1 9

Data Constraint

對于20%的數據:n<=100
對于40%的數據:n<=1000
對于60%的數據:n<=8000
對于80%的數據:n<=100000
對于100%的數據:0<n<=700000;ai<=1000;1<=bi,ci<=n;di<=1000。
數據保證一個點的加速器性能絕對小于等于它的所有的邊所耗費的能量，保證所有節點都可以到達,保證沒有數據與樣例相同。

Hint

提示：
樣例解釋：
如果以第一個點為根，則需要耗費0(到1)+1(到2)+2(到3)+6(到4)=9的能量值。
如果以第二個點為根，則需要耗費2(到1)+0(到2)+4(到3)+5(到4)=11的能量值。
如果以第三個點為根，則需要耗費1(到1)+2(到2)+0(到3)+7(到4)=10的能量值。
如果以第四個點為根，則需要耗費5(到1)+3(到2)+7(到3)+0(到4)=15的能量值。
很明顯以第一個點為根是最優的。 做法：其實并不是每個點都要建一次樹，我們可以在一個點為整棵樹的根節點時，以它的答案來更新它的兒子節點的答案，這樣實際上只會涉及一條邊貢獻的改變。 代碼如下： 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #define LL long long 5 #define N 1000007 6 using namespace std; 7 struct edge 8 { 9 LL to, next, w; 10 }e[N * 2]; 11 LL zs[N], n, a[N], ls[N * 2], ans, root, site, cnt; 12 bool v[N]; 13 14 void add(LL x, LL y, LL z) 15 { 16 e[++cnt].to = y; 17 e[cnt].next = ls[x]; 18 e[cnt].w = z; 19 ls[x] = cnt; 20 } 21 22 void dfs(LL x, LL sum) 23 { 24 root += sum; 25 for (int i = ls[x]; i; i = e[i].next) 26 { 27 if (v[e[i].to]) continue; 28 v[e[i].to] = 1; 29 dfs(e[i].to, sum + (e[i].w - a[x])); 30 zs[x] += zs[e[i].to]; 31 } 32 zs[x]++; 33 } 34 35 void find(LL x, LL sum) 36 { 37 if (sum < ans) 38 { 39 ans = sum; 40 site = x; 41 } 42 else if (sum == ans) site = min(site, x); 43 for (int i = ls[x]; i; i = e[i].next) 44 { 45 if (v[e[i].to]) continue; 46 v[e[i].to] = 1; 47 find(e[i].to, sum + (n - zs[e[i].to]) * (e[i].w - a[e[i].to])- zs[e[i].to] * (e[i].w - a[x])); 48 } 49 } 50 51 int main() 52 { 53 freopen("yggdrasil.in", "r", stdin); 54 freopen("yggdrasil.out", "w", stdout); 55 scanf("%lld", &n); 56 for (int i = 1; i <= n; i++) 57 scanf("%lld", &a[i]); 58 for (int i = 1; i <= n - 1; i++) 59 { 60 LL x, y, z; 61 scanf("%lld%lld%lld", &x, &y, &z); 62 add(x, y, z); 63 add(y, x, z); 64 } 65 v[1] = 1; 66 dfs(1, 0); 67 ans = root; 68 site = 1; 69 memset(v, 0, sizeof(v)); 70 v[1] = 1; 71 find(1, root); 72 printf("%lld\n", site); 73 printf("%lld", ans); 74 } View Code

?

轉載于:https://www.cnblogs.com/traveller-ly/p/9461936.html

總結

以上是生活随笔為你收集整理的JZOJ 5776. 【NOIP2008模拟】小x游世界树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。