树上移动类贪心：1108T4 / CF1381D

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134297045

http://47.92.197.167:5283/contest/428/problem/4

我们定义关键点为有3条路径大于 ≥L\ge L 的点。

如果其中一个点可以到达关键点，那么就可行。这是一个充要条件。

我们以关键点为根，如果某个时刻两个点一个是另一个是父亲，那么一定可以开到关键点那里。

我们只需要两个端点轮流往他们子树最深处的地方走，显然走得会越来越深。另外一个点就用倍增往上跳即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 100010
//#define M
//#define mo
int n, m, i, j, k, T;
int dep[N], mxdep[N], s1[N], s2[N], s3[N]; 
int f[N][22], s, t, u, v, rt, leaf[N], L, tot; 
vector<int>G[N]; 

int lca(int x, int y) {
  if(x==y) return x; 
  if(dep[x]<dep[y]) swap(x, y); 
  for(int k=20; k>=0; --k)
    if(dep[f[x][k]]>=dep[y]) x=f[x][k]; 
  if(x==y) return x; 
  for(int k=20; k>=0; --k)
    if(f[x][k]!=f[y][k]) x=f[x][k], y=f[y][k]; 
  return f[x][0]; 
}

int tiao(int x, int k) {
	if(dep[x]<=k) return rt; 
	if(!k) return x; 
	for(int g=20; g>=0; --g) 
		if((1<<g)<=k) x=f[x][g], k-=(1<<g); 
	return x; 
}

void make(int k, int x) {
	if(k>s1[x]) s3[x]=s2[x], s2[x]=s1[x], s1[x]=k; 
	else if(k>s2[x]) s3[x]=s2[x], s2[x]=k; 
	else if(k>s3[x]) s3[x]=k; 
}

void dfs1(int x, int fa) {
	for(int y : G[x]) if(y!=fa) {
		dfs1(y, x); 
		make(s1[y]+1, x); 
	}
	debug("%d : %d %d %d\n", x, s1[x], s2[x], s3[x]); 
}

void dfs2(int x, int fa) {
	int k; 
	for(int y : G[x]) if(y!=fa) {
		if(s1[x]==s1[y]+1) k=s2[x]+1; else k=s1[x]+1; 
		make(k, y); 
		dfs2(y, x); 
	}
	debug("%d : %d %d %d\n", x, s1[x], s2[x], s3[x]); 
}

int dfs3(int x, int fa, int s) {
	if(x==t) return s; 
	for(int y : G[x]) if(y!=fa) {
		int k=dfs3(y, x, s+1); 
		if(k!=1e9) return k; 
	}
	return 1e9; 
}

void dfs4(int x, int fa) {
	dep[x]=dep[fa]+1; leaf[x]=1; 
	mxdep[x]=x; 
	for(int y : G[x]) if(y!=fa) {
		dfs4(y, x); f[y][0]=x; leaf[x]=0; 
		if(dep[mxdep[y]]>dep[mxdep[x]]) mxdep[x]=mxdep[y]; 
	}
}

bool pan(int u, int v) {
	int z=lca(u, v); 
//	if(T==885) debug("lca(%d %d) = %d\n", u, v, z); 
	return (u==z || v==z); 
}

signed main()
{
	freopen("chtholly.in", "r", stdin);
	  freopen("chtholly.out", "w", stdout);
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	T=read(); 
	while(T--) {
//		cout<<T<<" "; 
		n=read(); s=read(); t=read(); 
//		if(T==91352) debug("%d %d %d\n", n, s, t); 
		for(i=1; i<=n; ++i) G[i].clear(), s1[i]=s2[i]=s3[i]=leaf[i]=dep[i]=mxdep[i]=f[i][0]=0; 
		for(i=1; i<n; ++i) {
			u=read(); v=read(); 
			G[u].pb(v); G[v].pb(u); 
//			if(T==91352) debug("%d %d\n", u, v); 

		}
		dfs1(1, 0); dfs2(1, 0); L=dfs3(s, 0, 0); 
		for(i=1; i<=n; ++i) if(s3[i]>=L) break; 
//		if(T==885) 
		debug(">> %d %d\n", L, i); 
		if(i>n) { printf("NO\n"); continue; }
		rt=i; dfs4(rt, 0); 
		for(k=1; k<=20; ++k)
			for(i=1; i<=n; ++i) f[i][k]=f[f[i][k-1]][k-1]; 
		for(i=1; i<=n; ++i) debug("%lld ", leaf[i]); debug("\n"); 
		tot=1; 
		while(!pan(s, t) && tot<=2*n) {
			int d=max(dep[s], dep[t]); 
//			debug("[%lld %lld] %lld | %lld %lld\n", s, t, mxdep[s], mxdep[t], k); 
			k=dep[mxdep[s]]-dep[s]; s=mxdep[s]; t=tiao(t, k); 
			swap(s, t); 
//			if(T==885) 
			++tot; 
		}
		printf(pan(s, t) ? "YES\n" : "NO\n"); 
	}
	return 0;
}