时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
月出皎兮。佼人僚兮。舒窈纠兮。劳心悄兮。
机缘巧合之下，一女误入诗经之境。少女在桥上，望尽千里壮阔千山。只见画面瞬转，忽不慎跌入荷塘深处，左右尽是海草纠缠。少女心中惶惶，只见水中突然横现一行字，写着“
给一棵树有n个节点，根节点为1。
每个点有一个颜色，并且有一个权值，为当前这个节点颜色的数量。
对每个点输出，当前点以及子树中的最大匹配数。
当且仅当颜色不同可以匹配。
”。
你可以解救被困水中的少女吗？
比如：
颜色1的权值和为3，颜色2的权值和为2，那么最大匹配数就是2。
颜色1的权值和为3，颜色2的权值和为2，颜色3的权值和为1，那么最大匹配数就是3。
输入描述:
第一行输入一个n，代表树的节点个数。
接下来输入n-1行，每行2个数：u,v代表存在一条u到v的边。保证树连通。
接下来输入n行，每行2个数：x，y，代表点i的颜色和数量。
节点个数1<=n<=2e5
颜色总数1<=x<=2e5
每个点的数量1<=y<=1e3
输出描述:
输出有n行，从1到n分别代表当前点以及子树中的最大匹配。
示例1
输入
复制
4
1 2
1 3
2 4
1 3
3 1
2 2
2 3
说明
显然3,4号点只有1种颜色，故无法匹配，所以最大匹配为0.
对于2号点，颜色3有1个，颜色2有3个，所以最大匹配为1.
对于1号店，颜色1有3个，颜色2有5个，颜色3有1个，可以发现最大匹配为4.