洛谷P4228 [清华集训2017] 榕树之心 题解
题意：
一棵榕树可以抽象成一棵 \(n\) 个结点的有根树，其中结点编号为 \(1 \sim n\) ，而 \(1\) 号点就是根节点。初始时，树只有一号点，而心也在一号点。之后每一步，树都会长出一个新结点，即某个和当前已经存在的某个结点相邻的结点被加入了树中，之后，心会沿着心到新加结点的简单路径移动一步。这棵 \(n\)个结点的树有很多种生长的顺序，不同的顺序可能会导致最终心的位置不同。现在，Evan和Lyra想知道，哪些结点可能是心在生长过程结束时停留的位置呢？
例如一棵大小为 \(4\) 的树，连边为 \(\{\langle 1,2 \rangle,\langle 1,3 \rangle,\langle 1,4 \rangle\}\) ，我们有三种不同的生长顺序可以让心分别停留在 \(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\) 行，每行两个正整数 \(a_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\) 号点的答案。
数据范围：
\(T \leq 20,~n \leq 10^5\)
难得有点思路的清华集训题，然而还是不会。
这道题是一道性质题，建议先自己尝试一定时间再看题解（
注意到点 \(x\) 能成为最后的心的一个必要条件为 \(n-\mathtt{dep}(x)\) 为奇数。
推了几组小数据，发现根节点和其他的结点结论不一样，毕竟初始位置在根。
因此单独对根节点讨论，不难发现如果根的所有子树均不超过 \(\left\lfloor\frac{n}{2}\right\rfloor\) ，则心可以在根上。
否则最大的那个子树大于 \(\left\lfloor\frac{n}{2}\right\rfloor\) ，最后心只是有可能会跑到那棵子树去，也可能到其他子树。
考虑用 dp 维护子树内心可以到达的最小深度（钦定根的深度最小）
设 \(f_i\) 表示以 \(i\) 为根的子树中，通过合理操作，最终心的相对深度的最小值（心 \(k\) 相对于 \(i\) 的深度，\(d_k-d_i\) ）
注意到 \(f_i\) 与 \(i\) 所在子树的大小始终有着不同的奇偶性。
记 \(s\) 为 \(i\) 的重儿子。若 \(\mathtt{size}(s) \le \left\lfloor\frac{\mathtt{size}(i)}{2}\right\rfloor\) ，则心可以被拉回 \(i\) ，即 \(f_i = (\mathtt{size}(i) + 1) \bmod 2\) 。
否则心可能会跑到 \(s\) 中。记 \(c = \mathtt{size}(i) -1 -\mathtt{size}(c)\) ，也就是剩下的那些子树的大小。
- 若 \(c \ge f_s\) ，则心可以被拉回来，故 \(f_i = (\mathtt{size}(i) + 1 )\bmod 2\) 。
- 若 \(c < f_s\) ，此时心拉不回来，但是根据定义，只能尽力去拉，故 \(f_i = f_s - c + 1\) 。
最后根节点 \(1\) 能成为心等价于 \(f_1 = 0\) 。
接着考虑其他的点。首先先检验一下 \(n-\mathtt{dep}(x)\) 是不是奇数，不是肯定不行。
可以发现，前 \(\mathtt{dep}(x)\) 步一定会把 \(1\) 移到 \(x\) （否则不会更优）。
如果把 \(1 \leadsto x\) 这条链看成一个点，那么就变成了 \(x\) 为根的情况。
我们可以用换根dp来维护每个 \(x \ne 1\) ，缩点后“上方”子树的大小。
这个可以用重儿子+次重儿子来维护。
单次时间复杂度 \(\mathcal{O}(n)\) ，注意第三个测试点只输出一个。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N ((int)(1e5+15))
char ok[N];
int n,Q,w,pos=1,sz[N],F[N],fa[N],dep[N],s1[N],s2[N],head[N];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
int Max(int x,int y) { return sz[x] < sz[y] ? y : x; }
void dfs1(int u)
{
int &A = s1[u], &B = s2[u]; sz[u] = A = B = 0;
for(int i=head[u]; i; i=e[i].next)
{
int v = e[i].v; if(v == fa[u]) continue;
fa[v] = u; dep[v] = dep[u] + 1; dfs1(v); sz[u] += sz[v];
if(sz[A] < sz[v])
{
B = A, A = v;
}else if(sz[B] < sz[v]) B = v;
}
if(F[A] <= sz[u] - sz[A]) F[u] = (sz[u] & 1);
else F[u] = F[A] - (sz[u] - sz[A]) + 1; ++sz[u];
}
void dfs2(int u,int f)
{
int d = n - dep[u], s;
if(d & 1)
{
s = Max(s1[u], f);
ok[u] |= (F[s] <= d - 1 - sz[s]);
}
for(int i=head[u]; i; i=e[i].next)
{
int v = e[i].v;
if(fa[v] == u)
{ s = Max(f, (v == s1[u]) ? s2[u] : s1[u]); dfs2(v,s); }
}
}
void solve()
{
read(n); pos = 1; for(int i=1; i<=n; i++) head[i] = 0;
for(int i=1,u,v; i<n; i++){ read(u); read(v); addEdge(u,v); addEdge(v,u); }
dfs1(1); if(w==3) return pc((!F[1]) | 48),pc('\n'), void(0);
for(int i=1; i<=n; i++) ok[i] = '0'; ok[n+1] = 0;
dfs2(1,0); printf("%s\n", ok+1);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
read(w);read(Q); while(Q--) solve();
return 0;
}参考文献：
[1] https://yhx-12243.github.io/OI-transit/?redirect=580
这个题目背景蛮好的。
深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的Evan和Lyra再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是Evan和Lyra再也不是七八年前不经世事的少年了。
……
“已经快是严冬了，榕树的叶子还没落呢……”
“榕树是常绿树，是看不到明显的落叶季节的……”
“唉……想不到已经七年了呢。榕树还是当年的榕树，你却不是当年的你了……”
“其实又有什么是一成不变的呢，榕树常绿，翠绿树冠的宏观永恒，是由无数细小树叶的荣枯更迭组成的。在时间的流逝中一切都在不断变化着呢……”
“但你看这榕树，日日如此，季季如此，年年如此，仿佛亘古不变般，盘根错节，郁郁葱葱。我在想，或许成为一棵树更好吧，任时间从枝叶间流过，我只守这一片绿荫就好。”
“榕树固然长久，但在这无限的时光里，终归是要湮灭于尘土的。与其像榕树一般，植根于一方泥土中感受年复一年的四季更替。倒不如在有限的时间里看过尽可能多的世界吧。再说了，榕树虽生长缓慢，却依旧会在每年春天抽出一根新的枝条去向外探索的呢……”
“真的吗，榕树在她漫长的一生里，就是这样往外一步步探索的吗？”
“毕竟就算树冠看起来一成不变，榕树也会随着时间周期变化，春天到了自然就是生长的时候了，她也应当做出对应的表现吧……”
“相比于对季节更替做出本能的生长，我倒宁愿相信，榕树有一颗活跃的的，探索的心。”
“其实榕树是有心的，榕树刚刚种下的时候，心就在根的地方发芽了。以后每年春天榕树长出新枝条的时候，心就会向着新枝条的方向移动一点，这样就能更靠近外面的世界了。你看这头顶上的枝条，纵横交错，其实心已经在这枝杈间，移动了数十载了呢……”
“哇，也就是说，这密密麻麻的树杈中的某个地方，藏着这棵榕树的心吗？”
“没错，可是要知道它在哪，就得另花一番功夫了……”
“呀，这时候想想，一株树还是不如一个人好……比如你，要是这样贴上去的话，就能听到跳动的声音呢……”
