CF1381D The Majestic Brown Tree Snake/SS251114C. 历遍的树（inverse）

题意

给你一棵 \(n\) 个点的树。一条蛇在路径 \((x,y)\) 上。

蛇像火车一样移动。问蛇能否走到路径 \((y,x)\)，即反转。

\(x \neq y\)。要线性或者接近线性做法。

思路

蛇会怎么走？

大概是这样的：有一个以 \(u\) 为枢纽的三叉路，整个蛇在其中一条岔路的链上。面向 \(u\) 的为蛇头。

然后蛇正向整个开进另一条岔路，然后再倒着整个开进第三条岔路，最后正向开回去。

我们把合法的枢纽叫做关键点。当存在三条长度大于等于蛇长的岔路时，这个枢纽是合法的。

蛇想要开到这样的三叉路里，发现它很容易走到树的直径。

结论 1：若直径上不存在关键点，则整个树不存在关键点。否则直径上一定存在关键点。

结论 2：若蛇可以到达一个关键点，则蛇可以到达任意关键点。

结论 2-2：若存在答案，蛇一定可以到达直径上的关键点。

证明 1。

证毕。

证明 2。

直接借用上图。\((s,t)\) 是直径。

假设 \(u\) 是一个关键点。蛇可以到达 \(u\)。那么蛇直接开进岔路 \(a\)，然后开到 \(t\) 那里去即可。

所以一定可以从直径外一个关键点走到直径上的关键点。逆操作显然也成立。

显然也可以从直径上一个关键点走到直径上另一个关键点。

所以先求出树的直径。

找到直径上任意一个关键点 \(u\)。

如果蛇可以有一端在 \(u\) 上，则有解。

以 \(u\) 为根。若 \(x,y\) 是祖孙关系，蛇就可以开到根。

否则求出 \(x,y\) 的 LCA。

在它们变成祖孙关系之前，LCA 不变。

蛇会来回来回地走，每次正着/倒着走到最远的叶子。

如果蛇走到同一个位置，则返回无解。

因为蛇不会走到同一个位置，所以直接模拟即可。

总时间复杂度线性。

code

#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();
}