CF1381D The Majestic Brown Tree Snake

编程入门行业动态更新时间:2024-10-26 08:20:28

CF1381D The Majestic Brown Tree Snake

洛谷CF1381D The Majestic Brown Tree Snake

题目大意

给定一棵有 n n n个节点的树，树上有一条蛇，蛇覆盖了从蛇头 s s s到蛇尾 t t t的简单路径 ( s ≠ t ) (s\neq t) (s=t)。

蛇有两种移动方式：

蛇头向周围没有被覆盖的位置移动一个单位，蛇尾向蛇头的方向挪动一个单位
蛇尾向周围没有被覆盖的位置移动一个单位，蛇头向蛇尾的方向挪动一个单位

问蛇能否将头和尾的位置调换，即蛇头移动到 t t t、蛇尾移动到 s s s。能则输出 Y E S YES YES，否则输出 N O NO NO。

有 T T T组数据。

1 ≤ T ≤ 100 , 1 ≤ n ≤ 1 0 5 , ∑ n ≤ 1 0 5 1\leq T\leq 100,1\leq n\leq 10^5,\sum n\leq 10^5 1≤T≤100,1≤n≤105,∑n≤105

题解

记蛇的长度为 L L L（边的数量）。

记 p p p为关键点，当且仅当从 p p p出发有至少 3 3 3条边不相交且长度 ≥ L \geq L ≥L的链（记为 p p p的分支）。

显然如果阵型型的两端能到达某个关键点，阵型就能翻转，即：

如果两端能到达某个关键点，则两端就能到达所有关键点
如果两端不能到达某个关键点，阵型就不能翻转

结论1证明

设两个关键点为 p 1 p_1 p1和 p 2 p_2 p2，阵型的一端为 p 1 p_1 p1。由定义可知 p 1 p_1 p1至少有一个分支不为阵型所在的分支，且不在 p 1 → p 2 p_1\to p_2 p1→p2的路径上，此时把阵型移动到这个分支中，再随着 p 1 → p 2 p_1\to p_2 p1→p2的路径移动就可以到达 p 2 p_2 p2。

结论2证明

如果阵型不能到达直径（非两端的某个点也算），就可以把这条直径删去。因此我们可以归纳成更小的树来证明。
\qquad
此时阵型一定能到达直径，并且离不开直径。
\qquad
反证法：如果阵型能离开直径（ x → y x\to y x→y），记离开的那个点为 u u u，这说明 d i s ( x , u ) ≥ L dis(x,u)\geq L dis(x,u)≥L且 d i s ( y , u ) ≥ L dis(y,u)\geq L dis(y,u)≥L（因为直径是这棵树上最长的一条链）。又因为阵型在第三个分支上，所以 u u u是关键点，与条件矛盾，所以原命题成立。
\qquad
同时说明阵型中一定有至少一条边永远在直径上，这条边决定了阵型的方向，所以阵型不能翻转。

我们以某个端点 s s s为根。

我们可以先判断每个点是不是关键点，用两次 d f s dfs dfs分别求向子树方向的分支和向祖先方向的分支的长度，维护最长分支、次长分支和次次长分支，如果一个点的次次长分支 ≥ L \geq L ≥L，则这个点是关键点；否则，这个点不是关键点。

如果整个图都没有关键点，则阵型不能翻转。

然后，我们维护端点 s s s向下可以移动到的位置和端点 t t t可以向上移动到的位置，如果 s s s和 t t t能够移动到的位置有交集，那么它们必定可以到达某个关键点，于是就可以翻转。否则，它们就到不了对方的位置，也就不能翻转了。

我们可以用双指针维护 s s s和 t t t分别能到达的位置，比如 s s s能到达一个新位置，就更新这个位置对 t t t的贡献。

时间复杂度为 O ( n ) O(n) O(n)。

可以参考代码帮助理解。

code

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int T,n,s,t,dep[N+5],mx[N+5],tf[N+5],w[N+5][3];
vector<int>v,g[N+5];
void pt(int u,int x){if(x>w[u][0]){w[u][2]=w[u][1];w[u][1]=w[u][0];w[u][0]=x;}else if(x>w[u][1]){w[u][2]=w[u][1];w[u][1]=x;}else if(x>w[u][2]) w[u][2]=x;
}
void dfs1(int u,int fa){dep[u]=dep[fa]+1;mx[u]=0;for(int v:g[u]){if(v==fa) continue;dfs1(v,u);pt(u,mx[v]+1);mx[u]=max(mx[u],mx[v]+1);}
}
void dfs2(int u,int fa){for(int v:g[u]){if(v==fa) continue;if(mx[v]+1==w[u][0]) pt(v,1+w[u][1]);else pt(v,1+w[u][0]);dfs2(v,u);}
}
bool dfs3(int u,int fa){tf[u]=fa;mx[u]=0;bool fl=(u==t);for(int v:g[u]){if(v==fa) continue;if(dfs3(v,u)) fl=1;else mx[u]=max(mx[u],mx[v]+1);}return fl;
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&s,&t);for(int i=1;i<=n;i++){g[i].clear();w[i][0]=w[i][1]=w[i][2]=0;}for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);g[x].push_back(y);g[y].push_back(x);}dep[0]=-1;dfs1(s,0);dfs2(s,0);bool fl=0;for(int i=1;i<=n;i++) fl|=(w[i][2]>=dep[t]);if(!fl){printf("NO\n");continue;}dfs3(s,0);v.clear();v.push_back(mx[t]);while(t!=s){t=tf[t];v.push_back(mx[t]);}int len=v.size(),l=0,r=len-1;int L=v[r],R=len-1-v[l];while(l<r){if(l<L){++l;R=min(R,len-1-(v[l]-l));}else if(r>R){--r;L=max(L,v[r]-(len-1-r));}else break;}if(l==r) printf("YES\n");else printf("NO\n");}return 0;
}