Description
给定一棵 $n$ 个点的树（$1le nle 10^5$），树上有一条蛇，蛇覆盖了从蛇头 $S$ 到蛇尾 $T$ 的简单路径（$S eq T$）。
蛇可以有两种移动方式：
1. 蛇头向周围没有被覆盖的位置移动一个单位，蛇尾向蛇头的方向挪动一个单位；
2. 蛇尾向周围没有被覆盖的位置移动一个单位，蛇头向蛇尾的方向挪动一个单位。
问蛇能否将头和尾的位置调换，即蛇头移动到 $T$、蛇尾移动到 $S$。
多次询问（不超过 $100$ 组），每次给定树和 $S,T$。
Solution
发现如果存在某个点能找出以它开始的，长度大于等于蛇的三条不相交路径，并且蛇能到达该点，那么蛇就可以在此处调头，所以就能首尾互换
符合要求的点可以用一次DFS和一次换根DP完成
并且因为树连通，所以只要能到达任意一个符合要求的点，那么其他的就都能达到
判定蛇是否能到达，令任意一个符合的点为根，可以让蛇轮流向头尾方向的最深的点移动，如果蛇的一端成为另一端的父节点，那么就可以到达
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int t,n,S,T,tot,head[100005],dep[100005],maxlen[100005][2],maxdep[100005][2],cnt[100005],fa[100005][21],d[100005],root,temp; bool vst[100005]; struct Edge { int to,nxt; }edge[200005]; inline int read() { int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } void dfs1(int k,int f) { dep[k]=dep[f]+1; for(int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if(v!=f) dfs1(v,k); } } void dfs2(int k,int f) { maxdep[k][0]=maxdep[k][1]=k,maxlen[k][0]=maxlen[k][1]=0; for(int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if(v!=f) { dfs2(v,k); if(maxlen[v][0]+1>maxlen[k][1]) maxlen[k][1]=maxlen[v][0]+1,maxdep[k][1]=maxdep[v][0]; if(maxlen[k][0]<maxlen[k][1]) swap(maxlen[k][0],maxlen[k][1]),swap(maxdep[k][0],maxdep[k][1]); if(maxlen[v][0]+1>=dep[T]-1) cnt[k]++; } } } void dfs3(int k,int f) { for(int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if(v!=f) { if(maxdep[v][0]==maxdep[k][0]) { if(maxlen[k][1]+1>=dep[T]-1) cnt[v]++; if(maxlen[k][1]+1>maxlen[v][1]) maxlen[v][1]=maxlen[k][1]+1,maxdep[v][1]=maxdep[k][1]; } else { if(maxlen[k][0]+1>=dep[T]-1) cnt[v]++; if(maxlen[k][0]+1>maxlen[v][1]) maxlen[v][1]=maxlen[k][0]+1,maxdep[v][1]=maxdep[k][0]; } if(maxlen[v][1]>maxlen[v][0]) swap(maxlen[v][1],maxlen[v][0]),swap(maxdep[v][1],maxdep[v][0]); dfs3(v,k); } } } bool check() { for(int i=1;i<=n;i++) if(cnt[i]>=3) return root=i,true; return false; } void dfs4(int k,int f) { d[k]=k,fa[k][0]=f,dep[k]=dep[f]+1; for(int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if(v!=f) { dfs4(v,k); if(dep[d[v]]>dep[d[k]]) d[k]=d[v]; } } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=20;~i;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if(x==y) return x; for(int i=20;~i;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } bool check2() { if(temp==S||temp==T) return true; for(int i=1;i<=n;i++) { int x=d[S],s=dep[x]-dep[S]; if(vst[x]) return false; if(s>=dep[T]-dep[temp]) return true; for(int j=20;~j;j--) if((1<<j)<=s) T=fa[T][j],s-=(1<<j); S=x,vst[x]=true,swap(S,T); } return false; } int main() { //freopen("data.txt","r",stdin); //freopen("B.txt","w",stdout); t=read(); for(;t;t--) { memset(head,0,sizeof(head)); memset(vst,false,sizeof(vst)); memset(cnt,0,sizeof(cnt)); tot=0; n=read(),S=read(),T=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); edge[++tot]=(Edge){v,head[u]},head[u]=tot; edge[++tot]=(Edge){u,head[v]},head[v]=tot; } dfs1(S,0); dfs2(S,0); dfs3(S,0); if(!check()) { puts("NO");continue; } dfs4(root,0); for(int i=1;i<=20;i++) for(int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1]; temp=lca(S,T); if(check2()) puts("YES"); else puts("NO"); } return 0; }