[Luogu P4228] [LOJ 2330] 榕树之心
深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的Evan和Lyra再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是Evan和Lyra再也不是七八年前不经世事的少年了。
……
“已经快是严冬了，榕树的叶子还没落呢……”
“榕树是常绿树，是看不到明显的落叶季节的……”
“唉……想不到已经七年了呢。榕树还是当年的榕树，你却不是当年的你了……”
“其实又有什么是一成不变的呢，榕树常绿，翠绿树冠的宏观永恒，是由无数细小树叶的荣枯更迭组成的。在时间的流逝中一切都在不断变化着呢……”
“但你看这榕树，日日如此，季季如此，年年如此，仿佛亘古不变般，盘根错节，郁郁葱葱。我在想，或许成为一棵树更好吧，任时间从枝叶间流过，我只守这一片绿荫就好。”
“榕树固然长久，但在这无限的时光里，终归是要湮灭于尘土的。与其像榕树一般，植根于一方泥土中感受年复一年的四季更替。倒不如在有限的时间里看过尽可能多的世界吧。再说了，榕树虽生长缓慢，却依旧会在每年春天抽出一根新的枝条去向外探索的呢……”
“真的吗，榕树在她漫长的一生里，就是这样往外一步步探索的吗？”
“毕竟就算树冠看起来一成不变，榕树也会随着时间周期变化，春天到了自然就是生长的时候了，她也应当做出对应的表现吧……”
“相比于对季节更替做出本能的生长，我倒宁愿相信，榕树有一颗活跃的的，探索的心。”
“其实榕树是有心的，榕树刚刚种下的时候，心就在根的地方发芽了。以后每年春天榕树长出新枝条的时候，心就会向着新枝条的方向移动一点，这样就能更靠近外面的世界了。你看这头顶上的枝条，纵横交错，其实心已经在这枝杈间，移动了数十载了呢……”
“哇，也就是说，这密密麻麻的树杈中的某个地方，藏着这棵榕树的心吗？”
“没错，可是要知道它在哪，就得另花一番功夫了……”
“呀，这时候想想，一株树还是不如一个人好……比如你，要是这样贴上去的话，就能听到跳动的声音呢……”
……
题目描述一棵榕树可以抽象成一棵 n 个结点的有根树，其中结点编号为 1∼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.123
最终停留在 3 号点：
从1生长出2，心从1移动到2, 从1生长出4，心从2移动回1, 从1生长出3，心从1移动到3.123
最终停留在 4 号点：
从1生长出2，心从1移动到2, 从1生长出3，心从2移动回1, 从1生长出4，心从1移动到4.123
而我们可以证明，不存在任何一种可能的生长顺序使得心停留在 1 号点。
输入输出格式 输入格式：从标准输入读入数据。
输入第一行一个两个正整数 W,T ，分别表示子任务编号（在样例中 W=0 ）和数据组数，接下来是 T 组数据的描述，对于每组数据：
第一行一个正整数 n 表示树上结点的个数。
接下来 n−1 行，每行两个正整数 ai,bi ，表示编号 ai,bi 的结点间有一条树边，保证 ai≠bi 并且输入的 n−1 条边恰好构成了一棵树。
输出格式：输出到标准输出。
若输入的 W 不等于 3 ，对于每组数据输出一行一个长度为 n 的 01 字符串，表示编号为 1∼n 的结点是否有可能是心最后所在的位置，若 01 字符串对应位是 1 则表示可能，为 0 则表示不可能。
若输入的 W 等于 3 ，则对每组数据输出一个字符表示 1 号点的答案。
输入输出样例
输入样例#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
123456789101112131415161718192021 输出样例#10111 000101 0000001010123
说明
TestPoint 1[10pts]
T≤50;n≤15 。
TestPoint 2[10pts]
T≤20;n≤105 。除了 1 号点之外，每个点度数（包括父亲）不超过 2 。
TestPoint 3[10pts]
T≤200;n≤100 。只输出一个字符表示 1 号点答案，即保证 1 号点答案正确即可。
TestPoint 4[35pts]
T≤20;n≤103 。
TestPoint 5[35pts]
T≤20;n≤105 。
解题分析先考虑TestPoint3的10分。我们可以发现，在考虑能否停留在一个节点A来说， 我们只需要考虑其最难消掉的最大的子树的大小。
因为所有其它子树间可以互相抵消位移，所以我们关心的就是最大子树fir[A]能够在自己的子树中抵消到什么程度。如果抵消后可得的最小值lef[fir[A]]≤其它子树中的点的总和，那么说明我们可以把所有子树几乎抵消完（与子树大小的奇偶性有关，如果为偶数则可以消完，奇数则剩1）。 如此操作， 我们一遍DFS即可AC。
再考虑其它TestPoint。其实和TestPoint3的不同在于一个”换根”操作。我们进行第二次DFS， 向下跳的时候随时更新路径上的最大子树即可。注意到我们向最大子树内DFS时不能取到这个最大值， 所以我们还要维护一个次大子树。
细节见代码。
#include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> #include <cstring> #include <cctype> #define R register #define IN inline #define W while #define gc getchar() #define MX 100500 template <class T> IN void in(T &x) { x = 0; R char c = gc; W (!isdigit(c)) c = gc; W (isdigit(c)) x = (x << 1) + (x << 3) + c - 48, c = gc; } int T, typ, dot, q, cnt; int head[MX], siz[MX], fir[MX], sec[MX], lef[MX], dep[MX], ans[MX], del[MX]; struct Edge { int to, nex; }edge[MX << 1]; IN void addedge(const int &from, const int &to) { edge[++cnt] = {to, head[from]}; head[from] = cnt; } void DFS(const int &now, const int &fa) { siz[now] = 1; del[now] = fir[now] = sec[now] = 0; for (R int i = head[now]; i; i = edge[i].nex) { if(edge[i].to == fa) continue; dep[edge[i].to] = dep[now] + 1; DFS(edge[i].to, now); siz[now] += siz[edge[i].to]; if(siz[edge[i].to] > siz[fir[now]]) sec[now] = fir[now], fir[now] = edge[i].to; else if(siz[edge[i].to] > siz[sec[now]]) sec[now] = edge[i].to; //预处理最大和次大子树 } if(siz[now] - 1 - siz[fir[now]] >= lef[fir[now]]) lef[now] = (siz[now] - 1) % 2; //当前点可以消到的剩余深度 else lef[now] = lef[fir[now]] - (siz[now] - 1 - siz[fir[now]]); ++lef[now]; } void solve(const int &now, const int &fa) { ans[now] = 0; if(!((siz[1] - dep[now]) % 2))//只有当可用点总数为偶数时才可能两边消完 { int cut = del[now]; if(siz[cut] < siz[fir[now]]) cut = fir[now]; if(siz[1] - dep[now] - siz[cut] >= lef[cut]) ans[now] = 1; } for (R int i = head[now]; i; i = edge[i].nex) { if(edge[i].to == fa) continue; del[edge[i].to] = del[now]; if(edge[i].to != fir[now] && siz[fir[now]] > siz[del[edge[i].to]]) del[edge[i].to] = fir[now]; //取不到最大子树 else if(siz[sec[now]] > siz[del[edge[i].to]]) del[edge[i].to] = sec[now]; solve(edge[i].to, now); } } int main(void) { int a, b; in(typ); in(T); W (T--) { memset(head, cnt = 0, sizeof(head)); in(dot); dep[1] = 1; for (R int i = 1; i < dot; ++i) in(a), in(b), addedge(a, b), addedge(b, a); DFS(1, 0); solve(1, 0); if(typ == 3) printf("%d", ans[1]);//注意特判 else for (R int i = 1; i <= dot; ++i) printf("%d", ans[i]); puts(""); } }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081相关知识
【DP】花店橱窗布置 (ssl 1626/luogu 1854)
竞赛技巧
榕树的寓意，榕树图片
榕树
榕树介绍 榕树盆景怎么养 榕树的特点
【榕树盆景】榕树盆景掉叶子,榕树盆景怎么养,修剪,图片
榕树图片
榕树盆景怎么养，榕树盆景图片
#种植# 榕树...
榕树怎么养榕树养殖方法和注意事项
网址: [Luogu P4228] [LOJ 2330] 榕树之心 https://m.huajiangbk.com/newsview1345904.html
| 上一篇: 榕树作文专题资料 |
下一篇: 花卉：榕树盆景冬天掉叶子怎么办？ |
