[AGC018F] Two Trees
题意翻译
给定两棵都是$N$个节点的有根树$A,B$,节点均从$1..N$标号。
我们需要给每个标号定一个权值,使在两棵树上均满足任意节点子树权值和为$1$或$-1$
输出任意一种解,需要判断无解
$N\leqslant 100000$
题目描述
[problemUrl]: https://atcoder.jp/contests/agc018/tasks/agc018_f
$ N $ 頂点からなる根付き木が $ 2 $ つあります。 どちらの木の頂点も、それぞれ $ 1 $ から $ N $ の番号がついています。 $ 1 $ つめの木の 頂点 $ i $ の親は $ A_i $ です。 なお、頂点 $ i $ が根のときは、$ A_i=-1 $です。 $ 2 $ つめの木の 頂点 $ i $ の親は $ B_i $ です。 なお、頂点 $ i $ が根のときは、$ B_i=-1 $です。
すぬけ君は、長さ $ N $ の整数列 $ X_1 $ , $ X_2 $ , $ ... $ , $ X_N $ であって、次の条件を満たすものを求めたいです。
- どちらの木のどの頂点についても、その頂点とその子孫の頂点の番号を $ a_1 $ , $ a_2 $ , $ ... $ , $ a_k $ としたとき、 $ abs(X_{a_1}\ +\ X_{a_2}\ +\ ...\ +\ X_{a_k})=1 $ が成り立つ。
条件を満たす整数列を作ることができるか判定し、存在するならば $ 1 $ つ求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ A_1 $ $ A_2 $ $ .. $ $ A_N $ $ B_1 $ $ B_2 $ $ .. $ $ B_N $
输出格式
条件を満たす整数列を作ることができない場合は、`IMPOSSIBLE` と出力せよ。 作ることができる場合は、まず $ 1 $ 行目に、`POSSIBLE` と出力せよ。 続いて、$ 2 $ 行目には条件を満たす整数列 $ X_1 $ , $ X_2 $ , $ ... $ , $ X_N $ を空白区切りで出力せよ。
输入输出样例
输入样例 #1
5
3 3 4 -1 4
4 4 1 -1 1
输出样例 #1
POSSIBLE
1 -1 -1 3 -1
输入样例 #2
6
-1 5 1 5 1 3
6 5 5 3 -1 3
输出样例 #2
IMPOSSIBLE
输入样例 #3
8
2 7 1 2 2 1 -1 4
4 -1 4 7 4 4 2 4
输出样例 #3
POSSIBLE
1 2 -1 0 -1 1 0 -1
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 10^5 $
- $ 1\ \leq\ A_i\ \leq\ N $ (頂点 $ i $ が $ 1 $ つ目の木の根でないとき)
- $ A_i\ =\ -1 $ (頂点 $ i $ が $ 1 $ つ目の木の根のとき)
- $ 1\ \leq\ B_i\ \leq\ N $ (頂点 $ i $ が $ 2 $ つ目の木の根でないとき)
- $ B_i\ =\ -1 $ (頂点 $ i $ が $ 2 $ つ目の木の根のとき)
- 入力はvalidな根付き木である。
### Sample Explanation 1
例えば、$ 1 $ つ目の木の頂点 $ 3 $ について見てみると、その頂点と子孫の頂点の番号は、$ 3,1,2 $ となっています。 出力例のように整数列を設定すると、$ abs(X_3+X_1+X_2)=abs((-1)+(1)+(-1))=abs(-1)=1 $ となっており、問題ありません。 他の頂点についても同じように確かめると、確かに出力例の整数列は条件を満たしています。
### Sample Explanation 2
この例では、どうやっても条件を満たす整数列は作れません。 よって、この例の答えは `IMPOSSIBLE` になります。