#P18158. -is-this-bitset-

-is-this-bitset-

-is-this-bitset-

给定一棵有 nn 个节点、以节点1为根的二叉树,每个节点至多有两个孩子。另给定两个长度为 nn 的整数数组 a,ba,b。

对于节点 ii,它的子集和问题是:能否从 ii 的所有祖先以及 ii 自身中选出一个子集 SS,使得

∑j∈Saj=bi?\sum_{j\in S} a_j=b_i?

允许选择空集。

你可以对数组 aa 进行至多5000次操作。每次选择一个下标 ii 和一个整数 xx,满足 1≤i≤n1\le i\le n、0≤x≤2⋅1060\le x\le2\cdot10^6,并令 ai:=xa_i:=x。

完成操作后,对每个节点求出它在修改后数组上的子集和问题答案。输出修改后的完整数组和所有答案。你不需要最小化操作次数。

输入格式

第一行一个整数 nn(1≤n≤3000001\le n\le300000)。

接下来 n−1n-1 行,每行两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n、u≠vu\ne v),表示树的一条无向边。保证这些边组成一棵以1为根的二叉树。

下一行 nn 个整数 a1,…,ana_1,\ldots,a_n(0≤ai≤20000000\le a_i\le2000000)。

最后一行 nn 个整数 b1,…,bnb_1,\ldots,b_n(0≤bi≤20000000\le b_i\le2000000)。

输出格式

第一行输出 nn 个整数 a1′,…,an′a'_1,\ldots,a'_n(0≤ai′≤20000000\le a'_i\le2000000),表示进行至多5000次操作后得到的数组。

下一行输出一个长度恰为 nn 的二进制字符串。第 ii 个字符为 1 当且仅当节点 ii 在数组 a′a' 上的子集和问题有解,否则为 0。

有多种合法输出时,可以输出任意一种。只要答案正确,也允许完全不修改数组。

样例 1

输入:

5
2 1
1 3
3 4
5 4
1 3 11 12 6
0 5 12 13 18

输出:

1 3 11 12 0
10110

样例方案把最后一个数改为0。节点1选择空集得到0;节点3选择节点1、3得到12;节点4选择节点1、4得到13。其他两个节点的目标不可达。

样例 2

输入:

1
2000000
2000000

输出:

2000000
1