一棵 nn 个点的树,树上有一条蛇(一条链),给出其头和尾(链的两端点)。你每次可以把头或尾往某一个方向移动,问是否能将头尾位置互换

n105n \le 10^5

CF 1381D

Solution

挺有意思的一道题

设蛇的长度为 LL,定义一个点为关键点当且仅当存在三条(或以上)从它出发的长度 L\ge L 的路径,则有性质:

  1. 若蛇能移动到某个关键点上,则它一定能翻转;否则不行

  2. 若蛇能移动到某个关键点上,则他一定能移动到其他任意一个关键点上

通过树形DP预处理,任意找到一个关键点 pp 作为根,将蛇按以下方式移动:

  1. 找到头节点子树内最深的叶子,将蛇头移动到其位置上

  2. 找到尾节点子树内最深的叶子,将蛇尾移动到其位置上

  3. 重复以上过程,直到头和尾存在祖孙关系。若移动了 O(n)O(n) 次仍不存在,则无解

预处理倍增数组即可模拟上述过程

Code

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1e5;
const int MAXM = MAXN * 2;
const int MAX_LOG = log2(MAXN + 5);

int N, sx, sy, L;
int e, Begin[MAXN + 5], Next[MAXM + 5], To[MAXM + 5];

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

pii F[MAXN + 5]; // 子树内最大深度
int G[MAXN + 5]; // 子树外最大深度
int anc[MAX_LOG + 1][MAXN + 5], fa[MAXN + 5], dep[MAXN + 5];

inline void init_L (int x, int f, int d)
{
if (x == sy) { L = d; return ; }
for (int i = Begin[x]; i; i = Next[i]) if (To[i] != f) init_L (To[i], x, d + 1);
}

inline void dfs_F (int x, int f)
{
fa[x] = f;
F[x] = mp (0, x);
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (y == f) continue;
dfs_F (y, x);
Chkmax (F[x], mp (F[y].x + 1, F[y].y));
}
}

inline void dfs_G (int x, int f)
{
static int key[MAXN + 5], prefix[MAXN + 5], suffix[MAXN + 5], val[MAXN + 5];
int p = 0;

for (int i = Begin[x]; i; i = Next[i]) if (To[i] != f) key[++p] = To[i], val[p] = F[To[i]].x + 1;

prefix[0] = suffix[p + 1] = 0;
for (int i = 1; i <= p; ++i) prefix[i] = max (prefix[i - 1], val[i]);
for (int i = p; i >= 1; --i) suffix[i] = max (suffix[i + 1], val[i]);

p = 0;
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (y == f) continue;
++p;
G[y] = max (G[x] + 1, max (prefix[p - 1], suffix[p + 1]) + 1);
}

for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (y == f) continue;
dfs_G (y, x);
}

}

inline int get_root ()
{
init_L (sx, 0, 0);

dfs_F (1, 0), dfs_G (1, 0);

for (int x = 1; x <= N; ++x)
{
int cnt = G[x] >= L;
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (y == fa[x]) continue;
if (F[y].x + 1 >= L) ++cnt;
}
if (cnt >= 3) return x;
}

return -1;
}

int dfn[MAXN + 5], efn[MAXN + 5], dfs_clock;

inline void dfs_anc (int x, int f)
{
anc[0][x] = f;
for (int i = 1; i <= MAX_LOG; ++i) anc[i][x] = anc[i - 1][anc[i - 1][x]];

dep[x] = dep[f] + 1;
dfn[x] = ++dfs_clock;

for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (y == f) continue;
dfs_anc (y, x);
}

efn[x] = dfs_clock;
}

inline int in_sub (int x, int f)
{
if (dfn[f] <= dfn[x] && dfn[x] <= efn[f]) return 1;
return 0;
}

inline int get_anc (int x, int d)
{
for (int i = MAX_LOG; i >= 0; --i) if (d >> i & 1)
x = anc[i][x];
return x;
}

inline void Solve ()
{
int o = get_root ();
// DEBUG (o);
if (o == -1) { puts("NO"); return; }

dfs_F (1, 0);
dfs_clock = 0;
dfs_anc (1, 0);

if (in_sub (sx, sy) || in_sub (sy, sx)) { puts("YES"); return ; }

int x = sx, y = sy, T = N;
if (F[x].x == 0) swap (x, y);

while (T--)
{
if (F[x].x == 0) { puts("NO"); return ; }

int d = F[x].x;
x = F[x].y, y = get_anc (y, min (d, dep[y] - 1));

if (in_sub (x, y)) { puts("YES"); return ; }

swap (x, y);
}

puts("NO");

}

inline void Input ()
{
N = read<int>(), sx = read<int>(), sy = read<int>();
for (int i = 1; i < N; ++i)
{
int x = read<int>(), y = read<int>();
add_edge (x, y);
add_edge (y, x);
}
}

inline void Init ()
{
for (int i = 1; i <= N; ++i) Begin[i] = 0;
e = 0;
}

int main () // 记得清空!!!!!!!!!!
{

#ifdef hk_cnyali
freopen("D.in", "r", stdin);
freopen("D.out", "w", stdout);
#endif

int Te = read<int>();

while (Te--)
{
Init ();
Input ();
Solve ();
}

return 0;
}