Codeforces 708C 树形DP

 

HDU 5834 Magic boy Bi Luo with his excited tree 树形DP

http://acm.hdu.edu.cn/showproblem.php?pid=5834

Magic boy Bi Luo with his excited tree

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

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?

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.

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

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

Sample Output

Case #1:
15
10
14
9
15

Author

UESTC

Source

2016中国大学生程序设计竞赛 - 网络选拔赛

题意

给定一个无根树,每走到一个未访问的点,获得的收益为该点的点权,每经过一条边,花费为该边的边权。问假设以第i个点为起点,获得的最大的收益。

思路

很显然的树形DP,在第一次DFS的时候,处理出在每个子树u中,访问每个u的子树v并返回u点获得最大收益subtree_max_back(如果访问某个u的子树的收益为负数,可以选择不访问它,那么收益就是0)。处理访问子树u时,停留在子树u中获得最大收益subtree_max_noback,以及具体停留在u的以哪个子节点为子树的子树中subtree_max_noback_idx。还需要维护停留在子树u中获得次大收益subtree_submax_noback

对于subtree_max_back值,就是选择访问u点的每一次子树并返回获得的收益,如果收益为负数就时收益为0。那么subtree_max_back就是一个求和的过程。

对于维护subtree_max_noback,枚举u的每一个子节点v,我们假设停留在这个子树v中,那么此时的收益就是subtree_max_back[u]减去访问v子树并返回的收益再加上访问v子树不返回的收益,具体运算,见GetValueNoBack函数。再将这个函数的用于更新subtree_submax_noback和subtree_max_noback以及subtree_max_noback_idx即可。

在第二次DFS的时候,我们传入fa_back和fa_noback两个参数,分别代表从u点访问父亲节点后并且回到u点获得的最大收益和从u点访问父亲节点后不再访问u点获得最大价值。那么很显然,从u点出发,要么停留在u的子树中,要么停留在非u子树,两个值取max就好了,即max(subtree_max_back[u] + fa_noback, subtree_max_noback[u] + fa_back)。

那么在给u的v传的时候(这里用fb和fnb表示),应该传多少呢?fb很容易想到,就是subtree_max_back[u]减去访问v子树并返回的收益,再加上fa_back。对于fnb参数,就有点不好想了。假设v不是subtree_max_noback_idx[u],那么这个fnb就可能停留在非u子树,也可能停留在非v的u的子树中(这个值直接就是subtree_max_noback[u]减去访问v子树并返回的收益),那么,这种情况下,fnb=max(fa_noback + subtree_max_back[u] - max(0, subtree_max_back[v] - 2 * l),fa_back + subtree_max_noback[u] - max(0, subtree_max_back[v] - 2 * l));那么对于v=subtree_max_noback_idx[u],就不能选择停留在v子树了,除了可以选择停留在非u子树,还可以次大值subtree_submax_noback[u]的哦!和上面一样,扣除问v子树并返回的收益即可。那么这种情况下fnb = max(fa_noback + subtree_max_back[u] - max(0, subtree_max_back[v] - 2 * l),fa_back + subtree_submax_noback[u] - max(0, subtree_max_back[v] - 2 * l));

然后继续DFS得出所有的答案。

 

Codeforces 581F Zublicanes and Mumocrates 树形DP 分组背包

F. Zublicanes and Mumocrates
time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

It's election time in Berland. The favorites are of course parties of zublicanes and mumocrates. The election campaigns of both parties include numerous demonstrations on n main squares of the capital of Berland. Each of the n squares certainly can have demonstrations of only one party, otherwise it could lead to riots. On the other hand, both parties have applied to host a huge number of demonstrations, so that on all squares demonstrations must be held. Now the capital management will distribute the area between the two parties.

Some pairs of squares are connected by (n - 1) bidirectional roads such that between any pair of squares there is a unique way to get from one square to another. Some squares are on the outskirts of the capital meaning that they are connected by a road with only one other square, such squares are called dead end squares.

The mayor of the capital instructed to distribute all the squares between the parties so that the dead end squares had the same number of demonstrations of the first and the second party. It is guaranteed that the number of dead end squares of the city is even.

To prevent possible conflicts between the zublicanes and the mumocrates it was decided to minimize the number of roads connecting the squares with the distinct parties. You, as a developer of the department of distributing squares, should determine this smallest number.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 5000) — the number of squares in the capital of Berland.

Next n - 1 lines contain the pairs of integers x, y (1 ≤ x, y ≤ n, x ≠ y) — the numbers of the squares connected by the road. All squares are numbered with integers from 1 to n. It is guaranteed that the number of dead end squares of the city is even.

Output

Print a single number — the minimum number of roads connecting the squares with demonstrations of different parties.

Sample test(s)
Input

Output

Input

Output

题意:一颗无根树,要求把每个节点涂成黑色或者白色,求叶子节点为黑色的数目=叶子节点为白色的数目等情况下,相邻两点颜色不同的数目最少。

思路:进行树形DP,先选取一个度>1的点作为根,用dp[u][j][k]表示在u点表示的这个子树中,它包含的叶子节点有j个被涂色为黑色,且u点的颜色为k(0/1),这种情况下相邻两点颜色不同的数目的最少值。对于每一个子树,进行分组背包,每个组必须要取一个元物品,详细的转移看代码。每个节点的初始dp[u][0][0]=dp[u][0][1]=0,其他状态尚未转移,全部设置为无效(INF);边界条件就是当u点位叶子节点的时候,dp[u][0][0]=0,dp[u][1][1]=0,dp[u][1][0]=INF。在枚举背包容量的时候,要注意容量的上限设置,否则会TLE的!!

代码: