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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include <bits/stdc++.h>
inline int rd() { int b = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) b = b * 10 + c - '0', c = getchar(); return b; }
const int N = 1e5 + 5;
int W, T, n, ans[N]; std::vector<int> G[N];
int size[N], son[N], dp[N];
void dfs1(int x, int fa) { size[x] = 1; for (int y : G[x]) { if (y != fa) { dfs1(y, x); if (size[y] > size[son[x]]) son[x] = y; size[x] += size[y]; } } int half = size[x] - 1 - size[son[x]]; if (half >= dp[son[x]] + 1) dp[x] = (size[x] - 1) & 1; else dp[x] = dp[son[x]] + 1 - half; }
void dfs2(int x, int fa, int all, int max) { int fir = max, sec = 0; for (int y : G[x]) { if (y != fa) { if (size[y] >= size[fir]) { if (size[fir] > size[sec]) sec = fir; fir = y; } else if (size[y] > size[sec]) { sec = y; } } } if (!(all & 1)) { int half = all - size[fir], cnt = 0; if (half >= dp[fir] + 1) cnt = all & 1; else cnt = dp[fir] - half; ans[x] = !cnt; } for (int y : G[x]) { if (y != fa) { dfs2(y, x, all - 1, y == fir ? sec : fir); } } }
inline void solve() { n = rd(); for (int i = 1; i < n; ++i) { int x = rd(), y = rd(); G[x].push_back(y); G[y].push_back(x); } dfs1(1, 0); dfs2(1, 0, n - 1, 0); int up = W == 3 ? 1 : n; for (int i = 1; i <= up; ++i) putchar(ans[i] + '0'); putchar('\n'); for (int i = 1; i <= n; ++i) { G[i].clear(); size[i] = son[i] = dp[i] = 0; ans[i] = 0; } }
int main() { freopen("data", "r", stdin); W = rd(), T = rd(); while (T--) solve(); return 0; }
|