专栏文章

题解：CF1381D The Majestic Brown Tree Snake

wwing_heart
CF1381D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8394z
此快照首次捕获于
2025/12/01 22:06
3 个月前
此快照最后确认于
2025/12/01 22:06
3 个月前
查看原文

CF1381D The Majestic Brown Tree Snake

更好的阅读体验

题意

给你一棵 nn 个点的树。一条蛇在路径 (x,y)(x,y) 上。
蛇像火车一样移动。问蛇能否走到路径 (y,x)(y,x)，即反转。
x≠yx \neq y。要线性或者接近线性做法。

思路

蛇会怎么走？
大概是这样的：有一个以 uu 为枢纽的三叉路，整个蛇在其中一条岔路的链上。面向 uu 的为蛇头。
然后蛇正向整个开进另一条岔路，然后再倒着整个开进第三条岔路，最后正向开回去。
我们把合法的枢纽叫做关键点。当存在三条长度大于等于蛇长的岔路时，这个枢纽是合法的。
蛇想要开到这样的三叉路里，发现它很容易走到树的直径。
结论 1：若直径上不存在关键点，则整个树不存在关键点。否则直径上一定存在关键点。
结论 2：若蛇可以到达一个关键点，则蛇可以到达任意关键点。
结论 2-2：若存在答案，蛇一定可以到达直径上的关键点。
证明 1。
证毕。
证明 2。
直接借用上图。(s,t)(s,t) 是直径。
假设 uu 是一个关键点。蛇可以到达 uu。那么蛇直接开进岔路 aa，然后开到 tt 那里去即可。
所以一定可以从直径外一个关键点走到直径上的关键点。逆操作显然也成立。
显然也可以从直径上一个关键点走到直径上另一个关键点。
所以先求出树的直径。
找到直径上任意一个关键点 uu。
如果蛇可以有一端在 uu 上，则有解。
以 uu 为根。若 x,yx,y 是祖孙关系，蛇就可以开到根。
否则求出 x,yx,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();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...