首页 > 代码库 > 2016中国大学生程序设计竞赛 - 网络选拔赛 C. Magic boy Bi Luo with his excited tree
2016中国大学生程序设计竞赛 - 网络选拔赛 C. Magic boy Bi Luo with his excited tree
Magic boy Bi Luo with his excited tree
Problem Description
Bi Luo is a magic boy, he also has a migic tree, the tree has N nodes , in each node , there is a treasure, it‘s value is V[i], and for each edge, there is a cost C[i], which means every time you pass the edge i , you need to pay C[i].
You may attention that every V[i] can be taken only once, but for some C[i] , you may cost severial times.
Now, Bi Luo define ans[i] as the most value can Bi Luo gets if Bi Luo starts at node i.
Bi Luo is also an excited boy, now he wants to know every ans[i], can you help him?
You may attention that every V[i] can be taken only once, but for some C[i] , you may cost severial times.
Now, Bi Luo define ans[i] as the most value can Bi Luo gets if Bi Luo starts at node i.
Bi Luo is also an excited boy, now he wants to know every ans[i], can you help him?
Input
First line is a positive integer T(T≤104) , represents there are T test cases.
Four each test：
The first line contain an integer N(N≤105).
The next line contains N integers V[i], which means the treasure’s value of node i(1≤V[i]≤104).
For the next N−1 lines, each contains three integers u,v,c , which means node u and node v are connected by an edge, it‘s cost is c(1≤c≤104).
You can assume that the sum of N will not exceed 106.
Four each test：
The first line contain an integer N(N≤105).
The next line contains N integers V[i], which means the treasure’s value of node i(1≤V[i]≤104).
For the next N−1 lines, each contains three integers u,v,c , which means node u and node v are connected by an edge, it‘s cost is c(1≤c≤104).
You can assume that the sum of N will not exceed 106.
Output
For the i-th test case , first output Case #i: in a single line , then output N lines , for the i-th line , output ans[i] in a single line.
Sample Input
154 1 7 7 7 1 2 61 3 12 4 83 5 2
Sample Output
Case #1:151014915
Author
UESTC
Source
2016中国大学生程序设计竞赛 - 网络选拔赛
题意： 给出一棵树，每个点当经过它时有一个获益，每个点的获益只能计算一次，每条边当经过它都有一个花费，需要重复计算。 询问从每个点出发，随意走的最大收益。
题解： 树形dp。 比赛时没有A掉。。。队友没有采取我的思路写，按照他们推的公式写了。。。 （其实是当时我在写其他题，我写完他们直接上了。。。实际上不用那么急， （当时比赛结束还有1.5h，好好整理思路写说不定就过了 其实我觉得我的思路是比较简单明了的。。 今天写了一下，从整理题目思路在内到AC，只花了1h，一发就AC了。。。 设f[i]代表每个点出去随便走不一定回来的最大收益和次大收益（一对数）， 个g[i]代表每个点出去随便走一定要回来的最大收益。 按照bfs序扫两遍。 第一遍，按照bfs序倒着扫： 统计每个点只能往下走的 f 和 g。 这部分是非常简单的dp，方程 g[i] = sigma(max(0, g[child] - 2 * costOfEdge)) f[i] = max(g[i], g[i] - max(0, g[child] - 2 * costOfEdge) + f[child] + costOfEdge) 计算f时先将孩子对g[i]的贡献减去加上本次贡献就行了。 第二遍，按照bfs序正着扫： 统计每个点的f和g，加入父亲的影响。 也就是说此时的f和g的意义变为不仅仅可以往下走还可以往父亲边走，就是随便走。 统计时类似，先减去自己对父亲的影响，再利用父亲的f和g更新自己。 转移方程这里写的不方便，具体可以查看代码。 最后每个点的f值就是答案。 因为f值不会比g值小，这点可以从定义或者方程看出。
1 const int N = 100010; 2 int head[N], son[N * 2], val[N * 2], nex[N * 2], tot; 3 int w[N], n; 4 struct FirstAndSecondMax { 5 pair<int, int> first, second; 6 7 inline void init(int val, int id) { 8 first = second = make_pair(val, id); 9 } 10 11 inline void addAll(int w) { 12 first.first += w, second.first += w; 13 } 14 15 inline void updata(int val, int id) { 16 pair<int, int> now = make_pair(val, id); 17 if(first < now) swap(first, now); 18 if(second < now) swap(second, now); 19 } 20 21 inline int getMax(int except) { 22 return first.second == except ? second.first : first.first; 23 } 24 } f[N]; 25 int g[N]; 26 // f -> maximum of paths that need not go back 27 // g -> maximum of paths that need to go back 28 #define cg(origin, cost) (max(0, origin - 2 * cost)) 29 #define cf(origin, cost) (max(0, origin - cost)) 30 // cg -> contribution to g 31 // cf -> contribution to f 32 int ans[N]; 33 34 inline void init() { 35 for(int i = 0; i < n; ++i) f[i].init(w[i], i); 36 for(int i = 0; i < n; ++i) head[i] = -1; 37 tot = 0; 38 } 39 40 inline void addEdge(int u, int v, int w) { 41 son[tot] = v, val[tot] = w, nex[tot] = head[u]; 42 head[u] = tot++; 43 } 44 45 int que[N], fa[N], valfa[N]; 46 inline void bfs(int st) { 47 int len = 0; 48 fa[st] = -1, valfa[st] = INF, que[len++] = st; 49 for(int idx = 0; idx < len; ++idx) { 50 int u = que[idx]; 51 for(int tab = head[u], v; tab != -1; tab = nex[tab]) 52 if((v = son[tab]) != fa[u]) 53 fa[v] = u, valfa[v] = val[tab], que[len++] = v; 54 } 55 } 56 57 inline void solve() { 58 bfs(1); 59 60 for(int idx = n - 1; idx >= 0; --idx) { 61 int u = que[idx]; 62 g[u] = w[u]; 63 for(int tab = head[u], v; tab != -1; tab = nex[tab]) 64 if((v = son[tab]) != fa[u]) 65 g[u] += cg(g[v], val[tab]); 66 f[u].init(g[u], u); 67 for(int tab = head[u], v; tab != -1; tab = nex[tab]) 68 if((v = son[tab]) != fa[u]) 69 f[u].updata(g[u] - cg(g[v], val[tab]) + 70 f[v].getMax(u) - val[tab], v); 71 } 72 73 for(int idx = 0; idx < n; ++idx) { 74 int u = que[idx]; 75 if(fa[u] != -1) { 76 int faContributeIt = g[fa[u]] - cg(g[u], valfa[u]); 77 int lastg = g[u]; 78 g[u] += cg(faContributeIt, valfa[u]); 79 f[u].addAll(cg(faContributeIt, valfa[u])); 80 f[u].updata(f[fa[u]].getMax(u) - cg(lastg, valfa[u]) 81 - valfa[u] + lastg, fa[u]); 82 } 83 ans[u] = f[u].getMax(-1); 84 } 85 86 for(int i = 0; i < n; ++i) printf("%d\n", ans[i]); 87 } 88 89 int main() { 90 int testCase; 91 scanf("%d", &testCase); 92 for(int testIndex = 1; testIndex <= testCase; ++testIndex) { 93 printf("Case #%d:\n", testIndex); 94 scanf("%d", &n); 95 for(int i = 0; i < n; ++i) scanf("%d", &w[i]); 96 init(); 97 for(int i = 1, u, v, w; i < n; ++i) { 98 scanf("%d%d%d", &u, &v, &w); 99 --u, --v;100 addEdge(u, v, w), addEdge(v, u, w);101 }102 solve();103 }104 return 0;105 }
2016中国大学生程序设计竞赛 - 网络选拔赛 C. Magic boy Bi Luo with his excited tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。