0%

「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$ 的所有点必须已经被选

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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;
}