题解：CF1381D The Majestic Brown Tree Snake
wing_heart
·
·
题解
CF1381D The Majestic Brown Tree Snake
更好的阅读体验
题意
给你一棵 n 个点的树。一条蛇在路径 (x,y) 上。
蛇像火车一样移动。问蛇能否走到路径 (y,x)，即反转。
## 思路
蛇会怎么走？
大概是这样的：有一个以 $u$ 为枢纽的三叉路，整个蛇在其中一条岔路的链上。面向 $u$ 的为蛇头。
然后蛇正向整个开进另一条岔路，然后再倒着整个开进第三条岔路，最后正向开回去。
-----------
我们把合法的枢纽叫做关键点。当存在三条长度大于等于蛇长的岔路时，这个枢纽是合法的。
蛇想要开到这样的三叉路里，发现它很容易走到树的直径。
------------
结论 1：若直径上不存在关键点，则整个树不存在关键点。否则直径上一定存在关键点。
结论 2：若蛇可以到达一个关键点，则蛇可以到达任意关键点。
结论 2-2：若存在答案，蛇一定可以到达直径上的关键点。
--------------
证明 1。
证毕。
-----------
证明 2。
直接借用上图。$(s,t)$ 是直径。
假设 $u$ 是一个关键点。蛇可以到达 $u$。那么蛇直接开进岔路 $a$，然后开到 $t$ 那里去即可。
所以一定可以从直径外一个关键点走到直径上的关键点。逆操作显然也成立。
显然也可以从直径上一个关键点走到直径上另一个关键点。
-----------
所以先求出树的直径。
找到直径上任意一个关键点 $u$。
如果蛇可以有一端在 $u$ 上，则有解。
以 $u$ 为根。若 $x,y$ 是祖孙关系，蛇就可以开到根。
否则求出 $x,y$ 的 LCA。
在它们变成祖孙关系之前，LCA 不变。
蛇会来回来回地走，每次正着/倒着走到最远的叶子。
如果蛇走到同一个位置，则返回无解。
因为蛇不会走到同一个位置，所以直接模拟即可。
总时间复杂度线性。
## code
```cpp
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace wing_heart {
constexpr int N=1e5+7;
int T,n;
int h,t,len;
int lca;
vector<int> to[N];
int dep[N],mxdep[N],fa[N],gson[N];
int rt;
int dfs0(int u,int f) {
fa[u]=f;
dep[u]=dep[f]+1;
int x = u;
for(int v : to[u]) if(v^f) {
int p = dfs0(v,u);
if(dep[p]>dep[x]) x=p;
}
return x;
}
void getlen() {
len=1;
int u=h,v=t;
if(dep[u]<dep[v]) swap(u,v);
while(dep[u]>dep[v]) ++len, u=fa[u];
while(u!=v) len+=2, u=fa[u], v=fa[v];
}
void findrt(int u,int fa) {
dep[u]=dep[fa]+1;
mxdep[u]=dep[u];
int cnt=0;
for(int v : to[u]) if(v^fa) {
findrt(v,u);
mxdep[u]=max(mxdep[u],mxdep[v]);
if(mxdep[v]-dep[u]+1>=len) ++cnt;
}
if(dep[u]>=len && cnt>=2) rt=u;
}
void init(int u,int f) {
fa[u]=f;
dep[u]=dep[f]+1;
mxdep[u]=dep[u];
gson[u]=0;
for(int v : to[u]) if(v^f) {
init(v,u);
mxdep[u]=max(mxdep[u],mxdep[v]);
if(mxdep[v] > mxdep[gson[u]]) gson[u]=v;
}
}
void getlca() {
int u=h,v=t;
if(dep[u]<dep[v]) swap(u,v);
while(dep[u]>dep[v]) u=fa[u];
while(u!=v) u=fa[u],v=fa[v];
lca=u;
}
void main() {
sf("%d",&T);
while(T--) {
sf("%d%d%d",&n,&h,&t);
rep(i,1,n) to[i].clear();
rep(i,1,n-1) {
int u,v;
sf("%d%d",&u,&v);
to[u].push_back(v), to[v].push_back(u);
}
int u = dfs0(1,0); // 找到直径的一端
getlen(); // 求出蛇长
rt=0;
findrt(u,0); // 找到关键点
if(!rt) {
puts("NO");
continue;
}
init(rt,0);
getlca();
int deph=dep[h],dept=dep[t];
while(lca!=h && lca!=t) {
int cdeph=mxdep[h];
if(cdeph-dep[lca]+1>=len) {
t=lca;
break;
}
while(gson[h]) h=gson[h], t=fa[t];
int cdept=mxdep[t];
if(cdept-dep[lca]+1>=len) {
h=lca;
break;
}
while(gson[t]) t=gson[t], h=fa[h];
if(cdeph==deph && cdept==dept) {
puts("NO");
break;
}
deph=cdeph, dept=cdept;
}
if(lca==h || lca==t) puts("YES");
}
}
}
int main() {
wing_heart :: main();
}
```