k - 路径（hard vension）

题号：NC279411
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：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$ ，输出一个整数，表示所有的 $k$ - 路径的最大权值，假如不存在，输出 $-1$ 。

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

输入描述:

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

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

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

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

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

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

输出描述:

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

示例1

输入

复制

1
5
1 2 1 2 2
1 -2 5 6 -7
2 3
3 5
3 4
1 5

输出

复制

-1 9 -1 -1 -1

说明

在第一个测试用例中，可能存在的  - 路径有 ，路径  的权值为 ，路径  的权值为 ，路径  的权值为 ，取最大，所以对于  - 路径，输出 。

示例2

输入

复制

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

输出

复制

7 -1 11 24 -1 -1 -1 -1 -1