[LOJ#2330]「清华集训 2017」榕树之心
试题描述
深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的Evan和Lyra再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是Evan和Lyra再也不是七八年前不经世事的少年了。
……
“已经快是严冬了，榕树的叶子还没落呢……”
“榕树是常绿树，是看不到明显的落叶季节的……”
“唉……想不到已经七年了呢。榕树还是当年的榕树，你却不是当年的你了……”
“其实又有什么是一成不变的呢，榕树常绿，翠绿树冠的宏观永恒，是由无数细小树叶的荣枯更迭组成的。在时间的流逝中一切都在不断变化着呢……”
“但你看这榕树，日日如此，季季如此，年年如此，仿佛亘古不变般，盘根错节，郁郁葱葱。我在想，或许成为一棵树更好吧，任时间从枝叶间流过，我只守这一片绿荫就好。”
“榕树固然长久，但在这无限的时光里，终归是要湮灭于尘土的。与其像榕树一般，植根于一方泥土中感受年复一年的四季更替。倒不如在有限的时间里看过尽可能多的世界吧。再说了，榕树虽生长缓慢，却依旧会在每年春天抽出一根新的枝条去向外探索的呢……”
“真的吗，榕树在她漫长的一生里，就是这样往外一步步探索的吗？”
“毕竟就算树冠看起来一成不变，榕树也会随着时间周期变化，春天到了自然就是生长的时候了，她也应当做出对应的表现吧……”
“相比于对季节更替做出本能的生长，我倒宁愿相信，榕树有一颗活跃的的，探索的心。”
“其实榕树是有心的，榕树刚刚种下的时候，心就在根的地方发芽了。以后每年春天榕树长出新枝条的时候，心就会向着新枝条的方向移动一点，这样就能更靠近外面的世界了。你看这头顶上的枝条，纵横交错，其实心已经在这枝杈间，移动了数十载了呢……”
“哇，也就是说，这密密麻麻的树杈中的某个地方，藏着这棵榕树的心吗？”
“没错，可是要知道它在哪，就得另花一番功夫了……”
“呀，这时候想想，一株树还是不如一个人好……比如你，要是这样贴上去的话，就能听到跳动的声音呢……”
……
一棵榕树可以抽象成一棵 \(n\) 个结点的有根树，其中结点编号为 \(1 \sim n\)，而 \(1\) 号点就是根节点。初始时，树只有一号点，而心也在一号点。之后每一步，树都会长出一个新结点，即某个和当前已经存在的某个结点相邻的结点被加入了树中，之后，心会沿着心到新加结点的简单路径移动一步。这棵 \(n\) 个结点的树有很多种生长的顺序，不同的顺序可能会导致最终心的位置不同。现在，Evan和Lyra想知道，哪些结点可能是心在生长过程结束时停留的位置呢？
例如一棵大小为 \(4\) 的树，连边为 \(\{<1,2>,<1,3>,<1,4>\}\)，我们有三种不同的生长顺序可以让心分别停留在 \(2,3,4\) 号节点上：
最终停留在 \(2\) 号点：
- 从 \(1\) 生长出 \(3\)，心从 \(1\) 移动到 \(3\),
- 从 \(1\) 生长出 \(4\)，心从 \(3\) 移动回 \(1\),
- 从 \(1\) 生长出 \(2\)，心从 \(1\) 移动到 \(2\).
最终停留在 \(3\) 号点：
- 从 \(1\) 生长出 \(2\)，心从 \(1\) 移动到 \(2\),
- 从 \(1\) 生长出 \(4\)，心从 \(2\) 移动回 \(1\),
- 从 \(1\) 生长出 \(3\)，心从 \(1\) 移动到 \(3\).
最终停留在 \(4\) 号点：
- 从 \(1\) 生长出 \(2\)，心从 \(1\) 移动到 \(2\),
- 从 \(1\) 生长出 \(3\)，心从 \(2\) 移动回 \(1\),
- 从 \(1\) 生长出 \(4\)，心从 \(1\) 移动到 \(4\).
而我们可以证明，不存在任何一种可能的生长顺序使得心停留在 \(1\) 号点。
输入
从标准输入读入数据。
输入第一行一个两个正整数 \(W, T\)，分别表示子任务编号（在样例中 \(W=0\)）和数据组数，接下来是 \(T\) 组数据的描述，对于每组数据：
第一行一个正整数 \(n\) 表示树上结点的个数。
接下来 \(n-1\) 行，每行两个正整数 \(ia_i,b_i\)，表示编号 \(a_i,b_i\) 的结点间有一条树边，保证 \(a_i \neq b_i\) 并且输入的 \(n-1\) 条边恰好构成了一棵树。
输出
输出到标准输出。
若输入的 \(W\) 不等于 \(3\)，对于每组数据输出一行一个长度为 \(n\) 的 \(01\) 字符串，表示编号为 \(1 \sim n\) 的结点是否有可能是心最后所在的位置，若 \(01\) 字符串对应位是 \(1\) 则表示可能，为 \(0\) 则表示不可能。
若输入的 \(W\) 等于 \(3\)，则对每组数据输出一个字符表示 \(1\) 号点的答案。
输入示例
0 3
4
1 2
1 3
1 4
6
1 2
1 3
1 4
4 5
5 6
10
1 2
1 3
3 4
3 5
3 6
4 7
7 8
8 9
9 10
输出示例
0111
000101
0000001010
数据规模及约定
Subtask 1[10pts]
\(T \leq 50; n \leq 15\)。
Subtask 2[10pts]
\(T \leq 20; n \leq 10^5\)。 除了 \(1\) 号点之外，每个点度数（包括父亲）不超过 \(2\)。
Subtask 3[10pts]
\(T \leq 200; n \leq 100\)。 只输出一个字符表示 \(1\) 号点答案，即保证 \(1\) 号点答案正确即可。
Subtask 4[35pts]
\(T \leq 20; n \leq 10^3\)。
Subtask 5[35pts]
\(T \leq 20; n \leq 10^5\)。
题解
考虑“生长”效果可以互相消去。先考虑只用判断能否到达根节点的子任务，我们发现当且仅当所有生长效果可以被消干净时才有可能最后停到根节点。
然后对于所有子树，最难消的肯定是最大的那颗子树，并且可以直观感觉到，最大的子树越小，越容易消干净，那么怎么量化这个感觉呢？
我们不妨设 \(elim(i)\) 表示对于子树 \(i\)，它最多能消掉的对数，令 \(siz_i\) 表示子树 \(i\) 中的节点数，\(s_m\) 为 \(i\) 最大的儿子。
那么当 \(siz_{s_m} \le siz_i - 1 - siz_{s_m}\) 时，可以用其他点把子树 \(s_m\) 全部消掉，如果其他点多出来了，它们之间可以互相消掉，唯一可能剩下的情况就是 \(siz_i - 1\) 为奇数，那么肯定会剩下一个节点。
当 \(siz_{s_m} > siz_i - 1 - siz_{s_m}\) 时，就考虑先让儿子 \(s_m\) 自己消，消到一定时候我们用兄弟助他一臂之力，看能不能消光；即 \(2 \cdot elim(s_m) + siz_i - 1 - siz_{s_m} \ge siz_{s_m}\) 时，能够全消光（奇数的话剩一个），否则能消的对数就是 \(elim(s_m) + siz_i - 1 - siz_{s_m}\)。
那么再考虑满分做法，对于节点 \(x\)，如果最终能够到达，相当于把 \(1 \sim x\) 的路径缩成新的根，然后其他的子树互相消就好了。这样我们就可以 dfs 的同时维护需要的信息（\(elim(i)\)，\(\mathrm{max}\{siz_i\}\) 等，这些信息可以很容易地合并，所以能够维护），然后遍历到的点就可以判断是否能够到达了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 100010
#define maxm 200010
int n, m, head[maxn], nxt[maxm], to[maxm];
void AddEdge(int a, int b) {
to[++m] = b; nxt[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; nxt[m] = head[a]; head[a] = m;
return ;
}
int siz[maxn], elim[maxn], ms[maxn], ms2[maxn];
void getElim(int u, int fa) {
siz[u] = 1;
ms[u] = ms2[u] = -1;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) {
getElim(to[e], u);
siz[u] += siz[to[e]];
if(ms[u] < 0) ms[u] = to[e];
else if(siz[to[e]] > siz[ms[u]]) ms2[u] = ms[u], ms[u] = to[e];
else if(ms2[u] < 0 || siz[to[e]] > siz[ms2[u]]) ms2[u] = to[e];
}
int others = 0;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa && to[e] != ms[u])
others += siz[to[e]];
if(others >= siz[ms[u]] - (elim[ms[u]] << 1)) elim[u] = siz[u] - 1 >> 1;
else elim[u] = elim[ms[u]] + others;
return ;
}
bool can[maxn];
void getCan(int u, int fa, int nsiz, int nelim, int nothers) {
if(ms[u] < 0) {
// printf("leave %d: %d %d %d\n", u, nsiz, nelim, nothers);
if(nothers >= nsiz - (nelim << 1) && !(nsiz + nothers & 1)) can[u] = 1;
else can[u] = 0;
return ;
}
int siza, ela, others = nothers + siz[u] - siz[ms[u]] - 1;
if(siz[ms[u]] > nsiz) siza = siz[ms[u]], ela = elim[ms[u]], others += nsiz;
else siza = nsiz, ela = nelim, others += siz[ms[u]];
// printf("node %d: %d %d %d\n", u, siza, ela, others);
if(others >= siza - (ela << 1) && !(siza + others & 1)) can[u] = 1;
else can[u] = 0;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) {
int nxsiz, nxelim, nxothers = nothers;
if(to[e] == ms[u]) {
nxothers += siz[u] - siz[to[e]] - 1 - (ms2[u] < 0 ? 0 : siz[ms2[u]]);
if(ms2[u] < 0 || nsiz > siz[ms2[u]]) nxsiz = nsiz, nxelim = nelim, nxothers += siz[ms2[u]];
else nxsiz = siz[ms2[u]], nxelim = elim[ms2[u]], nxothers += nsiz;
getCan(to[e], u, nxsiz, nxelim, nxothers);
}
else {
nxothers += siz[u] - siz[to[e]] - 1 - siz[ms[u]];
if(nsiz > siz[ms[u]]) nxsiz = nsiz, nxelim = nelim, nxothers += siz[ms[u]];
else nxsiz = siz[ms[u]], nxelim = elim[ms[u]], nxothers += nsiz;
getCan(to[e], u, nxsiz, nxelim, nxothers);
}
}
return ;
}
int main() {
int W = read(), T = read();
while(T--) {
n = read();
m = 0; memset(head, 0, sizeof(head));
rep(i, 1, n - 1) {
int a = read(), b = read();
AddEdge(a, b);
}
memset(elim, 0, sizeof(elim));
getElim(1, 0);
// rep(i, 1, n) printf("%d%c", elim[i], i < n ? ' ' : '\n');
getCan(1, 0, 0, 0, 0);
if(W != 3){ rep(i, 1, n) putchar((int)can[i] + '0'); putchar('\n'); }
else{ putchar((int)can[1] + '0'); putchar('\n'); }
}
return 0;
}