「UOJ 345」「清华集训2017」榕树之心

UOJ #345. 【清华集训2017】榕树之心

题目背景

深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。

……

“已经快是严冬了，榕树的叶子还没落呢……”

“榕树是常绿树，是看不到明显的落叶季节的……”

“唉……想不到已经七年了呢。榕树还是当年的榕树，你却不是当年的你了……”

“其实又有什么是一成不变的呢，榕树常绿，翠绿树冠的宏观永恒，是由无数细小树叶的荣枯更迭组成的。在时间的流逝中一切都在不断变化着呢……”

“但你看这榕树，日日如此，季季如此，年年如此，仿佛亘古不变般，盘根错节，郁郁葱葱。我在想，或许成为一棵树更好吧，任时间从枝叶间流过，我只守这一片绿荫就好。”

“榕树固然长久，但在这无限的时光里，终归是要湮灭于尘土的。与其像榕树一般，植根于一方泥土中感受年复一年的四季更替。倒不如在有限的时间里看过尽可能多的世界吧。再说了，榕树虽生长缓慢，却依旧会在每年春天抽出一根新的枝条去向外探索的呢……”

“真的吗，榕树在她漫长的一生里，就是这样往外一步步探索的吗？”

“毕竟就算树冠看起来一成不变，榕树也会随着时间周期变化，春天到了自然就是生长的时候了，她也应当做出对应的表现吧……”

“相比于对季节更替做出本能的生长，我倒宁愿相信，榕树有一颗活跃的的，探索的心。”

“其实榕树是有心的，榕树刚刚种下的时候，心就在根的地方发芽了。以后每年春天榕树长出新枝条的时候，心就会向着新枝条的方向移动一点，这样就能更靠近外面的世界了。你看这头顶上的枝条，纵横交错，其实心已经在这枝杈间，移动了数十载了呢……”

“哇，也就是说，这密密麻麻的树杈中的某个地方，藏着这棵榕树的心吗？”

“没错，可是要知道它在哪，就得另花一番功夫了……”

“呀，这时候想想，一株树还是不如一个人好……比如你，要是这样贴上去的话，就能听到跳动的声音呢……”

……

写这篇题解就是为了上面这一段话。

听说 OIer 都是文学家。

题意

有一棵 \(n\) 个点的树，初始时只有 \(1\) 号点，心也在 \(1\) 号点。

每次树会长出一个与当前某个已经存在节点相邻的点，心会沿着心到新点的简单路径移动一步。

现在已知树的最终形态，求所有生长顺序下哪些点可能成为心最终所在的位置。

\(T\) 组数据。

\(T\le 20, n\le 10^5\)。

做法

首先由于步数确定，把树黑白染色后会有一种颜色必然不能被走到。

考虑一个子问题，只需要求 \(1\) 号点是否能成为心最终的位置。

令 \(f_i\) 表示以 \(i\) 为根的子树，初始只有 \(i\) 号点，心也在 \(i\) 号点，按任意顺序加完所有点后心离 \(i\) 的最近距离。

答案即为 \([f_1=0]\)。

计算 \(f_u\) 时，找到一个 \(f_v\) 最大的儿子 \(v\)，长完这个子树之后心到 \(u\) 的距离最小是 \(f_v+1\)。之后如果心能够回到 \(u\)，通过调整选取顺序，最终必然可以停留在 \(u\) 或 \(u\) 的某个儿子上；如果不能，得到的也一定是最浅的方案。

---

考虑原来的问题，有点类似换根，再自上而下做一遍 dp 即可。

有一些细节是选取当前点的时候，当前点到 \(1\) 的所有点必须已经被选。

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}

const int N = 100005;
int num, n, W, T, h[N], f[N], siz[N], e[N<<1], pre[N<<1];
bool ans[N];
inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
void dfs1(int u, int fa=0){
	int mx=0;
	siz[u]=1;
	for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa){
		dfs1(e[i], u), siz[u]+=siz[e[i]];
		if(f[e[i]]>=f[mx]) mx=e[i];
	}
	int sum=0;
	for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa && e[i]!=mx) sum+=siz[e[i]];
	if(mx) f[u]=f[mx]+1-sum, f[u]=max(f[u], f[u]&1); else f[u]=0;
}
void dfs2(int u, int fa=0, int dep=0){
	int mx=fa, mx2=0, sum;
	for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa){
		if(f[e[i]]>f[mx]) mx2=mx, mx=e[i];
		else if(f[e[i]]>=f[mx2]) mx2=e[i];
	}
	if(mx==fa) sum=siz[u]; else sum=n-siz[mx]-1-dep;
	ans[u]=(((dep^n)&1) && sum>=f[mx]+1);
	int fmx=f[mx], fmx2=f[mx2];
	for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa){
		if(e[i]!=mx) f[u]=fmx+1-(sum-siz[e[i]]);
		else f[u]=fmx2+1-(mx2==fa?siz[u]-siz[mx]:n-siz[mx]-siz[mx2]-1-dep);
		f[u]=max(f[u], f[u]&1), dfs2(e[i], u, dep+1);
	}
}
inline void solve(){
	num=0, memset(h, 0, sizeof h);
	read(n);
	for(int i=1, x, y; i<n; ++i) read(x), read(y), add(x, y), add(y, x);
	dfs1(1), dfs2(1);
	for(int i=1; i<=(W==3?1:n); ++i) putchar('0'+ans[i]);
	putchar('\n');
}
int main() {
	read(W), read(T);
	while(T--) solve();
	return 0;
}