Description

给出一个无根树。树有N个点,边有权值。每个点都有颜色,是黑色、白色、
灰色这三种颜色之一,称为一棵三色树。
可爱的 Alice觉得,一个三色树为均衡的,当且仅当,树中不含有黑色结点
或者含有至多一个白色节点。然而,给出的三色树可能并不满足这个性质。
所以,Alice打算删去若干条边使得形成的森林中每棵树都是均衡的,花费
的代价等于删去的边的权值之和。请你计算需要花费的代价最小是多少。
注意,输入文件包含多组测试数据。

Input


第一行包含一个正整数 T,表示有 T组测试数据。接下来依次是 T组测试数
据。每组测试数据的第一行包含一个正整数 N。
第二行包含 N个 0、1、2之一的整数,依次表示点 1到点 N的颜色。其中,
0 表示黑色,1表示白色,2表示灰色。
接下来 N-1行,每行为三个整数ui、vi、c i,表示一条权值等于ci的边(ui, vi)。

Output

输出 T行,每行一个整数,依次表示每组测试数据的答案。

Sample Input


1
5
0 1 1 1 0
1 2 5
1 3 3
5 2 5
2 4 16

Sample Output

10

HINT

花费 10的代价删去边(1, 2)和边(2, 5)。

对于 100%的数据:1      ≤ N     ≤ 300 000   ,1 ≤ T  ≤ 5   ,0    ≤ ci<=10^9

觉得real非常非常妙的题啊 %了icefox以后才会做了 orz巨佬好强

题意:每个点有三种颜色 黑白灰 现在要求把这棵树变成一些满足以下要求的树 只有白点或者只有一个白点 黑点无所谓 求问将给定的图变成如上要求的最小代价  代价是每次可以断边权

那么设dp[x][i][j]表示当前节点在x号且x为根  有i个黑色j个白色的其他子树或者其他树都满足条件的最小代价是多少 那么不妨先以1当根 然后树形dp下 既然我的定义是以x为根 为什么树形dp也okay 因为最后我要求的是整张图满足条件即可 并没有说谁要做根 那么x节点上下几条边都可以断那不就okay 做转移的时候我枚举子树再枚举我当前节点的状态 (黑点数&白点数) 对于黑点>1的情况我直接累加在1上 对于白点>2的情况 我直接累加在2上  然后再枚举子树的状态(黑点数&白点数) 然后判断 转移到我现在来 要么我现在的黑点数&白点数是我+子树的 或者断开和子树的边 黑点数&白点数就是我自己的 比较下即可

 

 


elijahqi

本人蒟蒻qwq 欢迎加qq虐qwq 2922945330

发表评论

电子邮件地址不会被公开。 必填项已用*标注