#P18158. -is-this-bitset-
-is-this-bitset-
-is-this-bitset-
给定一棵有 个节点、以节点1为根的二叉树,每个节点至多有两个孩子。另给定两个长度为 的整数数组 。
对于节点 ,它的子集和问题是:能否从 的所有祖先以及 自身中选出一个子集 ,使得
允许选择空集。
你可以对数组 进行至多5000次操作。每次选择一个下标 和一个整数 ,满足 、,并令 。
完成操作后,对每个节点求出它在修改后数组上的子集和问题答案。输出修改后的完整数组和所有答案。你不需要最小化操作次数。
输入格式
第一行一个整数 ()。
接下来 行,每行两个整数 (、),表示树的一条无向边。保证这些边组成一棵以1为根的二叉树。
下一行 个整数 ()。
最后一行 个整数 ()。
输出格式
第一行输出 个整数 (),表示进行至多5000次操作后得到的数组。
下一行输出一个长度恰为 的二进制字符串。第 个字符为 1 当且仅当节点 在数组 上的子集和问题有解,否则为 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