簡要題意：（考慮到某些人搜題解只是懶得看題面）
特殊點從 \(1\) 號點出發，每次選擇一個與當前選擇連通塊相連的點，加入連通塊，并且把我們的特殊點向那個選的點移動一格。對每個點求是否能成為我們的特殊點的終點。\(1\) 處在一開始的連通塊之中。

不錯的一道題。但是如果要很快地寫對需要冷靜思考（像我就不知道在干什么）。像我這樣的菜雞看了題解才會……

先考慮簡單的部分，即 \(W = 3\)，只輸出 \(1\) 的答案。

先根據特殊點的深度的奇偶性來判斷一個點有沒有可能（即 \(dep_x + n\) 的奇偶性）。

根據套路，如果有一個子樹的大小大于總大小的一半，那么那個子樹顯然能貢獻很多，但是不一定會無解。如果不存在，顯然能構造出一個方案（即分成三部分，一個部分里只有一個，另外兩個部分大小分別都小于一半，顯然有解）。

所以現在只要考慮那個最大的子樹，如果我們把它消的小了，那么還是有可能的。記 \(f_i\) 為向 \(i\) 走能造成的最小的相對深度（不是相對 \(i\) 而是相對走到 \(i\) 的那個點，即 \(i\) 也會對這個深度產生貢獻。這樣做能方便各種地方的細節）。

顯然，考慮如果 \(u\) 向 最大的子樹 \(v\) 走，此時如果 \(sz_u - sz_v - 1\) 即其他子樹的大小是比 \(f_v\) 大的，又因為 \(sz_v > sz_u - sz_v - 1\)，那么顯然能構造出一種方案，使得 \(v\) 的貢獻與 \(sz_u - sz_v - 1\) 相差不超過 \(1\) 。所以直接根據奇偶性進行轉移，即 \(f_u = sz_u - 1 \mod 2\)。

但是如果這個比不上 \(f_v\) ，那么其他的子樹肯定是要拿去消 \(f_v\) 的，所以 \(f_u = f_v - (sz_u - sz_v - 1) + 1\)。

所以現在已經做完這個簡單的部分了。考慮其他點的情況。因為路徑上的點是必經的，所以如果把這條路徑縮成一個點，上述的過程依然能進行。（因為如果點可行，那就是對消的，那么在鏈上顯然可以）

所以我們仍維護那個最大的子樹。因為一條鏈都縮成一個點了，那么這些子樹都是原樹某個點的子樹。因此不必要考慮換根DP的各種細節，直接類似上面的過程處理下去即可。

注意數據的清空。同時因為變量初始化的原因，以及轉移沒推清楚，先RE了一發，又WA成45了一發。

#include <bits/stdc++.h>const int MAXN = 100010;int head[MAXN], nxt[MAXN << 1], to[MAXN << 1], tot; void addedge(int b, int e) {nxt[++tot] = head[b]; to[head[b] = tot] = e;nxt[++tot] = head[e]; to[head[e] = tot] = b; } int sz[MAXN], fir[MAXN], sec[MAXN]; int f[MAXN], ansl[MAXN], n; int cmp(int a, int b) { // a >= breturn sz[a] == sz[b] ? f[a] <= f[b] : sz[a] > sz[b]; } void gx(int & fir, int & sec, int v) {if (cmp(v, fir)) sec = fir, fir = v;else if (cmp(v, sec)) sec = v; } void dfs1(int u, int fa = 0) {sz[u] = 1;for (int i = head[u]; i; i = nxt[i])if (to[i] != fa) {dfs1(to[i], u);sz[u] += sz[to[i]];gx(fir[u], sec[u], to[i]);}if (!fir[u]) return ;int R = sz[u] - 1 - sz[fir[u]];if (R > f[fir[u]]) f[u] = sz[u] + 1 & 1; else f[u] = f[fir[u]] + 1 - R;// std::cout << u << ' ' << sz[u] << " : " << fir[u] << ' ' << sec[u] << " : " << f[u] << ' ' << R << std::endl; } void dfs2(int u, int fa = 0, int ma = 0, int dep = 0) {int t, v;gx(v = ma, t = 0, fir[u]);if (dep + n & 1)ansl[u] = n - dep - 1 - sz[v] >= f[v];for (int i = head[u]; i; i = nxt[i]) if (to[i] != fa) {gx(v = ma, t = 0, to[i] == fir[u] ? sec[u] : fir[u]);dfs2(to[i], u, v, dep + 1);} } int main() {// freopen("1.in", "r", stdin);std::ios_base::sync_with_stdio(false), std::cin.tie(0);int W, T; std::cin >> W >> T;while (T --> 0) {std::cin >> n;for (int i = 1, t1, t2; i < n; ++i) {std::cin >> t1 >> t2;addedge(t1, t2);}dfs1(1); dfs2(1);for (int i = 1; i <= (W == 3 ? 1 : n); ++i)std::cout << ansl[i];std::cout << '\n';memset(head, 0, n + 1 << 2); tot = 0;memset(ansl, 0, n + 1 << 2);memset(fir, 0, n + 1 << 2);memset(sec, 0, n + 1 << 2);memset(f, 0, n + 1 << 2);}return 0; }

轉載于:https://www.cnblogs.com/daklqw/p/11574871.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【清华集训2017】榕树之心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。