输入文件：tree.in 输出文件：tree.out 时间限制：4s 空间限制：512MB
Bob想要和Carrol玩游戏。但Carrol觉得玩游戏太无聊，就和Tuesday去写歌了。于是现在Bob来找你玩游戏。 这个游戏是这样的：给定一棵n个节点的树， 1号点为根节点，设v的父亲是f(v) 。其中每个节点有一个颜色，要么是黑色，要么是白色。不妨记第i个节点的初始颜色是ci。ci =0或1，表示黑色或白色。 在游戏开始时，Bob为每个节点选择一个目标颜色di，要求你经过若干次操作，将每个节点变成其目标颜色。你的操作是这样的： ●选定一个点u，将u,f(u),f(f(u)),…,fk-1 (u)这k个节点的颜色翻转（将白色节点变为黑色节点，将黑色节点变为白色节点）。其中k是游戏开始前确定的一个正整数。 只有u,f(u),f(f(u)),…,fk-1 (u)这k个节点均存在，你才能执行这样的操作。当然，你可以执行任意多次操作。 现在Bob要和你玩T次这样的游戏，每次你都想要知道你是否有可能完成要求，即通过若干次操作，将所有节点变成其目标颜色。**
●第一行仅一个数T≤10，表示这样的游戏的次数； ●接下来共有T组数据。对于每一组数据： ○第一行是两个正整数n,k，n表示树的大小，k的含义请参见题目描述。数据满足n,k≤2×105 ○接下来n-1行每行两个数u,v，表示树上有一条边(u,v) 。注意：输入并不保证边的方向。 ○接下来一行n个数c1 , c2，…，cn，表示初始颜色。 ○接下来一行n个数d1 , d2，…，dn，表示目标颜色。
输出包含T行，第i行对应第i次游戏的答案； 对于第i次游戏，如果你有可能完成任务，输出Yes，否则输出No 。
2 3 2 1 2 2 3 0 0 0 1 0 1 3 2 1 2 2 3 0 0 0 1 1 1
Yes No
●在第一个例子中，第一次选择2号点操作，1,2号点被翻转；第二次选择3 号点操作，2,3号点被翻转。即达成目标状态。 ●可以证明，无法将初始状态经过操作变为目标状态。
对于全部测试点：T≤10, k≤n≤2×105，保证数据给出的是一棵树。 对于前 10% 的数据，n≤5； 对于前 30% 的数据，n≤20； 对于前 50% 的数据，n≤2000； 对于前 70% 的数据，n≤50000； 对于全部数据，n≤2×105
AI代码
#include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; int f = 0; bool qqq[100]; memset(qqq, false, sizeof(qqq)); int qqq1 = t, qqq2 = 0; while(t--) { int n, k; cin >> n >> k; int a[n + 1]; memset(a, 0, sizeof(a)); for(int i = 1; i < n; i++) { int x, y; cin >> x >> y; a[y] = x; } bool b[n + 1], c[n + 1]; memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c)); for(int i = 1; i <= n; i++) { cin >> b[i]; } for(int i = 1; i <= n; i++) { cin >> c[i]; } if(n < k) { cout << "No"; continue; } else if(n == k) { cout << "No"; continue; } else { for(int i = n; i >= n - k; i--) { if(b[i] == c[i]) { continue; } int tmp = i; for(int j = 1; j <= k ; j++) { if(b[tmp] == 0) { b[tmp] = 1; } else if(b[tmp] == 1) { b[tmp] = 0; } tmp = a[tmp]; } int q; for(q = 0; q <= n; q++) { if(b[q] != c[q]) { break; } } q--; if(q == n) { f = 1; qqq[qqq2] = 1; qqq2++; } } if(f == 0) { qqq[qqq2] = 0; qqq2++; } } f = 0; } for(int i = 0; i < qqq1; i++) { if(qqq[i] == 1) { cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }