Algoogle

Algorithm for Programming Contest

Codeforces 430C Xor-tree

Category: Codeforces Tag: dfs, tree

Xor-tree

問題概要


頂点数nの根付き木の各頂点は0か1の値をとる.
ある頂点xを選んで値を反転させたら, その孫, 孫の孫, …の頂点も反転させる.
初期状態と目的状態があるとき最小の選択回数と, 選択する頂点を答えよ.

解法


根付き木なので根から順に見ていけばそこを反転するかどうかは一意に決まる.
dfsするときに1つおきの祖先の反転情報を2つもって, 交互に使えばよい.

コード


(430C.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define pb push_back
const int MAX = 100010;

vector<int> G[MAX], ans;
int N, s[MAX], t[MAX];


void dfs(int v, int u, int f, int g){
    if((s[v]^f) != t[v]) ans.pb(v+1), f ^= 1;
    for(int &w: G[v])if(w != u) dfs(w,v,g,f);
}

void solve(){
    dfs(0,-1,0,0);
    cout << ans.size() << endl;
    for(int &v: ans) cout << v << endl;
}

void input(){
    cin >> N;
    rep(i,N-1){
        int a, b; cin >> a >> b;
        a--; b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    rep(i,N) cin >> s[i];
    rep(i,N) cin >> t[i];
}

int main(){
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(12);
    input();
    solve();
    return 0;
}

Comments