AGC018 F : Two Trees(1700)
作成日：2017.07.27
最終更新日：2017.07.27
問題概要
$N$頂点からなる2つの根付き木$A,B$が与えられる。
頂点$i$に整数$X_i$を書き込んでいくが、これは2つの木で共通である。
数列$\{X_i\}$を適切に選ぶことで$A,B$いずれにおいても任意の部分木の頂点に書かれた整数の総和の絶対値が$1$になるようにできるか判定せよ。
また可能である時には数列$\{X_i\}$を具体的に構築せよ。
制約
$1 \leq N \leq 10^5$
$1 \leq A_i,B_i \leq N$（頂点$i$が木$A,B$の根でないとき）
$A_i,B_i = -1$（頂点$i$が木$A,B$の根であるとき）
入力は根付き木
考え方
ある頂点$v$に書き込まれる数$X_v$について考えるために、一方の木において$v$を根とする部分木を考える。
$v$の子を根とする部分木において$X_i$の総和は$1$または$-1$であり、これはともに$mod \: 2$で$1$である。
よって$mod \: 2$で考えると、$v$の子の数と部分木に書き込まれた数の総和から$X_v$を引いたものは等しい。
つまり条件を満たすためには、$X_v$と$v$の子の数は$mod \: 2$で考えると異ならなければならない。
このことから、木$A,B$においてある頂点$v$の子の数の偶奇が異なるならば不可能であることが分かる。
そうでない時を考えるが、簡単のために一方の木のみにおいて考え、$X_i$は$-1,0,1$のいずれかのみを取るとする。
この時、子の数が奇数である頂点においては$X_i = 0$であり、偶数である頂点においては$X_i = \pm 1$である。
また、子を根とする部分木で頂点に書き込まれた数の総和が$1$になるものの数と$-1$になるものの数は等しいか差が$1$でなければならない。
そこで、$X_i = \pm 1$となる頂点をペアにしていくことでこれを達成することを考える。
ここで各ペア$(u,v)$は$X_u = -X_v$が成り立つようにする。
任意の部分木において書き込まれる数の総和が$\pm 1$であることから、ペアにならない頂点がちょうど1つ存在する。
よって深さ優先探索においてこれを親に伝え、伝えられた親はそれらを貪欲にペアにしていくと目標が達成されることが分かる。
ペアを作ることを木$A,B$の両方で行い、ペア間に辺を張ったグラフを考える。
いずれの木においても、ある頂点がペアになるのは高々1回であるから、任意の頂点から出ている辺は高々2本である。
よって、グラフ内の各連結成分は枝分かれのない環または鎖になっている。
また環になっている時、木$A$に由来する辺と木$B$に由来する辺は交互に連なっているから、環内には偶数の頂点が存在する。
以上より、このグラフは二部グラフになっていることが分かるので、一方に$-1$、もう一方に$1$を割り当てることで数列$\{X_i\}$が構成できる。
ソースコード
マクロ等はこちら
const int MC = 100010;
int N;
int r[2]; //木の根(木Aは0,木Bは1,以下同様)
vector<int> V[2][MC]; //子の頂点番号
int p[MC][2]; //iのペア
int X[MC];
int dfs(int t , int q){
int z = 0;
for(auto u : V[t][q]){
int y = dfs(t,u);
if(z){
p[y][t] = z;
p[z][t] = y;
z = 0;
} else {
z = y;
}
}
return z ? z : q;
}
int main(){
scanf("%d" , &N);
repp(t,0,2){
repp(i,1,N+1){
int A;
scanf("%d" , &A);
if(A<0) r[t] = i;
else V[t][A].PB(i);
}
}
repp(i,1,N+1){
if((V[0][i].size() - V[1][i].size()) % 2){
printf("IMPOSSIBLE\n");
return 0;
}
}
printf("POSSIBLE\n");
dfs(0,r[0]);
dfs(1,r[1]);
repp(i,1,N+1){
if(V[0][i].size()%2){
printf("0%c" , i==N ? '\n' : ' ');
continue;
}
if(X[i]==0){
repp(k,0,2){
int q = i;
int t = k;
X[i] = 1;
while(p[q][t] > 0 && X[p[q][t]] == 0){
X[p[q][t]] = -X[q];
q = p[q][t];
t = 1-t;
}
}
}
printf("%d%c" , X[i] , i==N ? '\n' : ' ');
}
return 0;
}解法まとめ
ある頂点がもつ子の数の偶奇が木$A,B$で異なると不可能であり、それ以外の場合は可能。(33-39行)
各木においてペアを貪欲に作る。(8-21,40,41行)
構成された二部グラフにおいて$-1$と$1$を割り当てる。(47-58行)