k - 路径（mid vension）

题号：NC277178
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

这是问题的中等版本。三个版本的做法之间可能有交集。

给定一颗 $n$ 个点的无根树，每个节点有类型和权值，分别用 $c$ 和 $w$ 表示。一条简单路径的权值为这条路径包含的节点权值之和。

对于一个长度为 $len+1(len>1)$ 的序列 $a$ ，假如 $a_1=a_{len+1}=len$ ，并且 $a_2,a_3,...,a_{len}$ 是一个长度为 $len-1$ 的排列，那么称序列 $a$ 是 $len$ - 特殊排列。

假如从 $u$ 走到 $v$ 长度为 $k+1$ 的简单路径依次经过的节点类型组成的序列是一个 $k$ - 特殊排列，那么这个简单路径是一条 $k$ - 路径。

特别的，假如一条简单路径只由两个类型为 $1$ 的节点组成，那么这条路径是 $1$ - 路径。

对于 $k=1,2,3,...n$ ，输出一个整数，表示所有经过点 $x$ 的 $k$ - 路径的最大权值，假如不存在，输出 $-1$ 。

提示：本题输入输出数据量较大，建议选手使用快速的输入输出方式。

输入描述:

第一行输入一个整数 ，表示测试数据组数。接下来是  个测试用例。

每个测试用例第一行输入两个整数 。

第二行有  个数 ，表示每个节点的类型。

第三行有  个数 ，表示每个节点的权值。

然后  行，每一行有两个整数 ，表示有一条  到  的无向边。

保证所有测试用例  的和不超过 。

输出描述:

对于每个测试用例，输出一行，包含  个空格分隔的整数，表示答案。

示例1

输入

复制

1
8 1
1 2 3 4 2 2 4 3
7 -8 -5 4 10 1 -7 -9
1 2
2 3
3 4
1 7
1 5
1 6
1 8

输出

复制

-1 18 -15 -9 -1 -1 -1 -1

说明

在第一个测试用例中，简单路径  的权值为 ，并且这条简单路径的节点类型组成的序列为  是一个  - 特殊排列，所以这条简单路径是一个  - 路径，并且显然没有其它任何一条  - 路径的权值比这条路径的权值大，所以对于 ，输出 。

示例2

输入

复制

4
10 1
1 2 3 4 5 2 3 4 1 5
-5 9 7 8 3 -7 -10 -7 6 -1
1 2
2 3
3 4
4 5
10 9
1 6
1 7
1 10
1 8
10 1
1 2 3 4 5 5 3 2 4 2
-2 6 -1 4 10 3 4 -1 3 5
1 2
2 3
3 4
4 5
1 8
10 7
1 9
9 6
1 10
10 1
1 2 3 4 5 4 5 5 5 2
-1 -6 -3 7 8 8 5 9 -9 -5
1 2
2 3
3 4
4 5
1 10
7 9
1 6
1 9
1 8
10 1
1 2 3 4 5 5 2 5 5 3
-9 -9 6 -3 3 -9 9 -1 -3 -6
1 2
2 3
3 4
4 5
1 8
1 7
9 10
1 6
1 10

输出

复制

-1 -3 1 12 21 -1 -1 -1 -1 -1
-1 9 -1 10 -1 -1 -1 -1 -1 -1
-1 -12 -1 5 14 -1 -1 -1 -1 -1
-1 -9 -18 -1 -13 -1 -1 -1 -1 -1