[清华集训2017]榕树之心 [换根DP]

[清华集训2017]榕树之心

“榕树还是当年的榕树，你却不是当年的你了”

先只算根，发现就是要把子树配对，使得根不会动。那么从下往上考虑，因为在比较深的树里如果能匹配很多对，上面需要更多的时候就可以随便减少一些给上面用。那么尽量在深的地方匹配是优秀的。

考虑把子树分成若干堆，考虑用最大的一堆和其它的消除。发现最大的一堆过分大的时候，是消不干净的，这时候需要从子树中拿出来一些匹配。否则只取决于奇偶。

考虑计算其它点的答案：先把根顺着链拉到目标点，之后不动了。于是把链缩成一个点即可。

#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;
}