Codeforces Round #245 (Div. 2) C. Xor-tree DFS

题目链接:

http://codeforces.com/contest/430/problem/C

题意:

一棵以1为根节点的树，每个点都是1或者0,
选定一个节点x，当前值取反，x的孙子，孙子的孙子。。。均取反
然后问你最少翻转多少次可以到达目标位置，且翻转的是哪些点

题解一:

深度浅的点一定是受影响最小的（根节点只受自己的影响），所以从根依次向下递推处理

代码一:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 std::vector<int> G[maxn],ans;
19 int n;
20 int s[maxn],e[maxn];
21 
22 void dfs(int x,int f,int s1, int s2){ // s1表示当前点是否翻转，s2表示当前点的所有儿子们是否翻转
23     if(s[x]^s1 != e[x]){ 
24         ans.PB(x);
25         s1 ^= 1; // 如果不行， 必转
26     }
27 
28     for(auto v : G[x]){
29         if(v!=f)
30             dfs(v,x,s2,s1); // 走到下一层， 因为当前层的上一层的翻转状态和下一层的一样
31     }
32 }
33 
34 int main(){
35     n = read();
36     for(int i=1; i<n; i++){
37         int u=read(),v=read();
38         G[u].PB(v);
39         G[v].PB(u);
40     }
41 
42     for(int i=1; i<=n; i++)
43         s[i] = read();
44     for(int i=1; i<=n; i++)
45         e[i] = read();
46 
47     dfs(1,-1,0,0);
48 
49     cout << ans.size() << endl;
50     for(auto x : ans)
51         cout << x << endl;
52 
53     return 0;
54 }

题解二:

http://blog.csdn.net/qq_26122039/article/details/52914241
节点初始标志记在d1[]中，节点目标标志记在d2[]中，k1为1表示奇数节点标志改变，k2为1表示偶数节点标志改变.h表示节点深度
从根节点开始深搜，遇到节点j先通过k1, k2改变d1[j]的值，改变后若d1[j] != d2[j]则d1[j] ^= 1, 同时若该节点深度h为奇数，则该节点孩子中奇数深度的节点都要改变，所以k1 ^= 1,同理若h为偶数，则该节点孩子中偶数深度的节点都要改变，所以k2 ^= 1;

代码二:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 std::vector<int> G[maxn],ans;
19 int n;
20 int s[maxn],e[maxn];
21 
22 void dfs(int x,int f,int k1,int k2,int d){
23 
24     if(k1 && (d&1)){
25         s[x] ^= 1;
26     }
27     if(k2 && !(d&1)){
28         s[x] ^= 1;
29     }
30 
31     if(s[x] != e[x]){
32         ans.PB(x);
33         if(d&1) k1 ^= 1;
34         else k2 ^= 1;
35         s[x] ^= 1;
36     }
37 
38     for(auto v : G[x]){
39         if(v!=f)
40             dfs(v,x,k1,k2,d+1);
41     }
42 }
43 
44 int main(){
45     n = read();
46     for(int i=1; i<n; i++){
47         int u=read(),v=read();
48         G[u].PB(v);
49         G[v].PB(u);
50     }
51 
52     for(int i=1; i<=n; i++)
53         s[i] = read();
54     for(int i=1; i<=n; i++)
55         e[i] = read();
56 
57     dfs(1,-1,0,0,0);
58 
59     cout << ans.size() << endl;
60     for(auto i : ans)
61         cout << i << endl;
62 
63     return 0;
64 }

今天打了BC#92 看题解才知道auto的用法= =