Sparken's Tree

发布时间: 2018年8月14日 17:33   最后更新: 2018年8月14日 17:37   时间限制: 2000ms   内存限制: 256M

Sparken画了一棵树,为了使这棵树更加漂亮,她决定给这棵树涂上颜色。

她的手中现在有红、黄、蓝,三种颜色的画笔,所以她只能使用这三种颜色来给而这棵树上色。她不愿意让相同的颜色相邻,因为这会使得整棵树过于单调,所以如果她把某个点绘制成一种颜色,那么她就会把与之相邻的点绘制成其他的颜色。为了让这棵树在上色之后更加好看,她对每个点涂成每种颜色都有一个评估价值。她现在想知道在不使相邻结点同色的情况下,这棵树涂满颜色的最大评估价值总和是多少。

第一行是一个整数$T$,表示测试数据的组数。
对于每组测试数据:
第一行是一个正整数$n$,表示树的结点数量。
接下来$n-1$行,每行$2$个整数$u,v$表示$u$和$v$结点有一条边连接。
接下来$n$行,每行三个整数$x,y,z$分别表示把第$i$个节点染成红、黄、蓝的评估价值。
$T \leq 50$
$2 \le n \le 10 ^ {5}$
$1 \le u, v \le n$
$0 \le x,y,z \le 10 ^ {5}$
$\sum n \le 4 \times 10 ^ {5}$

对于每组测试数据,在一行内输出一个整数表示答案。

复制
1
3
1 2
1 3
3 2 1
4 3 2
3 4 3
10

三个点的颜色分别为:红、黄、黄,则答案为$3 + 3 + 4 = 10$。

dfs dp

ACM集训队暑期集训新生组队赛