本文讨论 CCPC Final 2023 J 的与官方解法（from Lynkcat）略有区别的线性解法。
题目传送门：CCPC Final 2023 J
题解视频传送门：第九届 CCPC 总决赛题解
我们设给出的序列为 \(q\)。
\(q_1\) 是一个特殊的点，因为它的所有祖先构成了一条链，这条链上的点的儿子可以不出现在合法的子段中。
构造方法：所有没有出现的儿子，把它们的子树整个地放在这个点的后面、\(q_1\) 的前面。
同时要指出，合法的子段就是取出这条链的一些儿子，按深度递减的顺序排列，然后按这个顺序链接它们子树的 DFS 序。
假设我们处理到 \(q_i\)。 不妨设 \(x = q_{i - 1}, y = q_i\)，一样地讨论两者的关系。
\(y\) 在 \(x\) 子树内
这个时候 \(y\) 必须是 \(x\) 的儿子，否则从 \(x\) 到 \(y\) 中间一定经过一个点 \(p\)，使得 \(p\) 是 \(x\) 的儿子且是 \(y\) 的祖先。
这个条件还是很好判断的。
\(y\) 不在 \(x\) 子树内
这个情况一般就是结束了某个子树的遍历，跳到另一个子树内了。
我们知道，从 \(x\) 到 \(y\) 如果有 \(k\) 条向下的边，那么 \(x\) 和 \(y\) 在 DFS 序上的距离至少为 \(k - 1\)。
所以这个时候只能有 \(1\) 条向下的边，那么 \(y\) 的父亲就会落在 \(1\) 到 \(x\) 的路径上，是 \(x\) 的祖先，这个点记为 \(p\)。
从 \(x\) 回溯到 \(p\)，意味着 \(p\) 子树内的点不能再被遍历了，我们就要判断它们是否有遗漏的点需要放在 \(x\) 和 \(y\) 之间。
注意特殊链上的点可以遗漏一些儿子，所以我们先考虑 \(p\) 不在特殊链上，\(x\) 到 \(p\) 中被访问的点的子树。
我们维护一个栈表示 \(1\) 到 \(x\) 路径上，在子段中（被访问过）的点 \(st_p\)。同时记录它们子树中被访问过的点的个数 \(cnt_p\)。
这里需要预处理每个点的子树大小 \(size_x\)。对于栈顶，如果 \(cnt_p \neq size_{st_p}\)，说明 \(st_p\) 子树不满，不合法。
否则将 \(st_p\) 弹出，\(cnt_p\) 加到新的栈顶 \(st_p^{\prime}\) 的 \(cnt_p^{\prime}\)，\(st_p^{\prime}\) 一定是 \(st_p\) 的父亲。
注意栈中的 \(p\) 不需要检查或弹出。完成之后插入 \(y\) 即可。
如果 \(p\) 在特殊链上，栈中就不存在 \(p\)。这种情况下，我们逐个检查和弹出整个栈即可。
再来讨论 \(p\) 在特殊链上的情况。
每当出现这种情况，\(y, p\) 的深度一定不减，而且同深度的 \(y\) 显然是同一个 \(p\) 的儿子。
所以当出现 \(y\) 深度增大时不合法。
会不会出现同一个儿子多次访问呢？考虑这个儿子 \(y\) 在不在特殊链上。
如果 \(y\) 不在特殊链上，进入 \(y\) 时一定要访问 \(y\)，我们的标记可以帮助排除。
如果 \(y\) 在特殊链上，则访问 \(q_1\) 时已经访问了 \(y\)，一定不合法。
实现中要注意：
是否被访问的标记应该采用撤销的方式清除，这样总的复杂度才能保持 \(O(\sum k)\) 而不退化为 \(O(nQ)\)。
可以预处理一个 DFS 序用于判断点对 \((x, y)\) 是否构成祖先与后代的关系。
代码
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
| #include <algorithm>
#include <cstdio>
namespace Input{
const int BUFFLEN = 1 << 20;
char buf[BUFFLEN | 2], *p1 = buf, *p2 = buf;
inline char getc(){
if(p1 == p2)
p1 = buf,
p2 = buf + fread(buf, 1, BUFFLEN, stdin);
return p1 == p2? EOF: *p1++;
}
inline bool isdgt(const char op){return op >= '0' && op <= '9';}
long long read(){
static long long res; static char op, f;
for(f = 0, op = getc(); !isdgt(op); op = getc()) f |= (op == '-');
for(res = 0; isdgt(op); op = getc()) res = res * 10 + (op ^ '0');
return f? -res: res;
}
}
using Input::read;
typedef long long ll;
const int N = 100010;
int head[N], ver[N << 1], nxt[N << 1], tot = 1;
int fa[N], dep[N], siz[N];
int dfn[N], num;
bool vis[N];
int q[N * 10], n;
int sta[N], sum[N], tp;
inline void addedge(int x, int y){
ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}
void dfs(int x){
dfn[x] = ++num;
siz[x] = 1;
for(int k = head[x], y; y = ver[k], k; k = nxt[k]){
if(y == fa[x]) continue;
fa[y] = x;
dep[y] = dep[x] + 1;
dfs(y);
siz[x] += siz[y];
}
}
bool chkson(int x, int y){
return dfn[x] < dfn[y] && dfn[y] < dfn[x] + siz[x];
}
void push(int x){
tp++;
vis[x] = 1;
sta[tp] = x;
sum[tp] = 1;
}
bool solve(){
int m = read(), ans = 1;
for(int i = 1; i <= m; ++i)
q[i] = read();
tp = 0;
sum[0] = 0;
push(q[1]);
for(int i = 2, x, y = q[1], mind = dep[q[1]]; x = y, y = q[i], i <= m && ans; ++i)
if(vis[y] || chkson(y, q[1])) ans = 0;
else if(chkson(x, y)){
if(dep[y] != dep[x] + 1) ans = 0;
push(y);
}
else{
int t = fa[y];
if(!chkson(t, x)) ans = 0;
if(siz[x] != 1) ans = 0;
while(tp){
if(sum[tp] != siz[sta[tp]]) ans = 0;
sum[tp - 1] += sum[tp];
if(chkson(y, sta[tp])) ans = 0;
if(sta[--tp] == t) break;
}
if(!vis[t]){
if(dep[y] > mind) ans = 0;
if(mind > dep[y]) mind = dep[y];
}
push(y);
}
for(int i = 1; i <= m; ++i)
vis[q[i]] = 0;
return ans;
}
signed main(int argc, char **argv){
n = read(); int T = read();
for(int i = 1, x, y; i < n; ++i){
x = read(); y = read();
addedge(x, y); addedge(y, x);
}
dfs(1);
while(T--)
puts(solve()? "Yes": "No");
return 0;
}
|