观察可得，若存在合法解，则一定存在一种解，使得每个人都不停顿地从起点走到终点。
因为如果一个人走到一半要停下来等另一个人走，显然这个人也可以选择先走或者等另一个人走完自己再走。
继续观察可得，当且仅当第 \(i, j\) 个人满足以下条件，它们之间的走的先后顺序能被确定：
- \(s_i\) 在 \(\text{path}(s_j, t_j)\) 上，则 \(i\) 比 \(j\) 先走；
- \(t_i\) 在 \(\text{path}(s_j, t_j)\) 上，则 \(i\) 比 \(j\) 后走。
建图跑拓扑排序即可。但是朴素建图边数太多了。
考虑把 \(u, v\) 之间的边通过树上的点中转。对于每个点再复制一份，形成 \(x_i, x'_i\)。考虑建图如下：对于第 \(i\) 个人，设 \(s_i \to t_i\) 的路径中，除 \(s_i\) 外走到的第一个点是 \(p\)，除 \(t_i\) 外走到的第一个点是 \(q\)。
- 对于 \(u \in \text{path}(s_i, q)\)，连边 \(i \to u\)；
- 对于 \(u \in \text{path}(p, t_i)\)，连边 \(u' \to i\)；
- 连边 \(t_i \to i, i \to s_i'\)。
这样，若 \(s_i\) 在 \(\text{path}(s_j, t_j)\) 上，可以通过 \(i \to s_i' \to j\) 从 \(i\) 到达 \(j\)；若 \(t_i\) 在 \(\text{path}(s_j, t_j)\) 上，可以通过 \(j \to t_i \to i\) 从 \(j\) 到达 \(i\)。并且这样建图不会造成多余的影响。
那我们还剩下的问题是，一个点向树上的一条路径上的所有点连边。
考虑树剖后线段树优化建图，边数是 \(O(n \log^2 n)\)，就可以通过了。
code
// Problem: P9520 [JOISC 2022 Day1] 监狱
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9520
// Memory Limit: 1 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 120050;
const int maxm = 3000000;
const int logn = 20;
int n, m, rt1, rt2, ntot, head[maxm], len, to[maxm * 30], nxt[maxm * 30], id[maxn][2], di[maxn], ind[maxm];
pii a[maxn];
vector<int> G[maxn];
inline void add_edge(int u, int v) {
to[++len] = v;
nxt[len] = head[u];
++ind[v];
head[u] = len;
}
int ls[maxm], rs[maxm], si[maxm], stot;
int fa[maxn], dep[maxn], son[maxn], sz[maxn], top[maxn], dfn[maxn], times, rnk[maxn];
int f[maxn][logn];
void build(int &p, int &q, int l, int r) {
p = ++stot;
q = ++stot;
si[p] = ++ntot;
si[q] = ++ntot;
if (l == r) {
add_edge(si[p], id[rnk[l]][0]);
add_edge(id[rnk[l]][1], si[q]);
return;
}
int mid = (l + r) >> 1;
build(ls[p], ls[q], l, mid);
build(rs[p], rs[q], mid + 1, r);
add_edge(si[p], si[ls[p]]);
add_edge(si[p], si[rs[p]]);
add_edge(si[ls[q]], si[q]);
add_edge(si[rs[q]], si[q]);
}
void update1(int rt, int l, int r, int ql, int qr, int u) {
if (ql <= l && r <= qr) {
add_edge(u, si[rt]);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) {
update1(ls[rt], l, mid, ql, qr, u);
}
if (qr > mid) {
update1(rs[rt], mid + 1, r, ql, qr, u);
}
}
void update2(int rt, int l, int r, int ql, int qr, int u) {
if (ql <= l && r <= qr) {
add_edge(si[rt], u);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) {
update2(ls[rt], l, mid, ql, qr, u);
}
if (qr > mid) {
update2(rs[rt], mid + 1, r, ql, qr, u);
}
}
int dfs(int u, int f, int d) {
fa[u] = f;
sz[u] = 1;
dep[u] = d;
int mx = -1;
for (int v : G[u]) {
if (v == f) {
continue;
}
::f[v][0] = u;
sz[u] += dfs(v, u, d + 1);
if (sz[v] > mx) {
son[u] = v;
mx = sz[v];
}
}
return sz[u];
}
void dfs2(int u, int tp) {
top[u] = tp;
dfn[u] = ++times;
rnk[times] = u;
if (!son[u]) {
return;
}
dfs2(son[u], tp);
for (int v : G[u]) {
if (!dfn[v]) {
dfs2(v, v);
}
}
}
inline int qlca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
return x;
}
inline void treeadd1(int x, int y, int u) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
update1(rt1, 1, n, dfn[top[x]], dfn[x], u);
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
update1(rt1, 1, n, dfn[x], dfn[y], u);
}
inline void treeadd2(int x, int y, int u) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
update2(rt2, 1, n, dfn[top[x]], dfn[x], u);
x = fa[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
update2(rt2, 1, n, dfn[x], dfn[y], u);
}
inline int jump(int x, int k) {
for (int i = 0; i <= 18; ++i) {
if (k & (1 << i)) {
x = f[x][i];
}
}
return x;
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= ntot; ++i) {
head[i] = ind[i] = 0;
}
len = ntot = stot = times = 0;
for (int i = 1; i <= n; ++i) {
fa[i] = dep[i] = son[i] = sz[i] = top[i] = dfn[i] = 0;
vector<int>().swap(G[i]);
}
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
for (int i = 1; i <= n; ++i) {
id[i][0] = ++ntot;
id[i][1] = ++ntot;
}
dfs(1, -1, 1);
dfs2(1, 1);
build(rt1, rt2, 1, n);
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &a[i].fst, &a[i].scd);
di[i] = ++ntot;
}
for (int j = 1; j <= 18; ++j) {
for (int i = 1; i <= n; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
for (int i = 1; i <= m; ++i) {
int x = a[i].fst, y = a[i].scd;
int xx = -1, yy = -1;
int lca = qlca(x, y);
if (x == lca) {
xx = jump(y, dep[y] - dep[lca] - 1);
} else {
xx = fa[x];
}
if (y == lca) {
yy = jump(x, dep[x] - dep[lca] - 1);
} else {
yy = fa[y];
}
treeadd1(x, yy, di[i]);
treeadd2(xx, y, di[i]);
add_edge(id[y][0], di[i]);
add_edge(di[i], id[x][1]);
}
static int q[maxm];
int hd = 1, tl = 0;
for (int i = 1; i <= ntot; ++i) {
if (!ind[i]) {
q[++tl] = i;
}
}
while (hd <= tl) {
int u = q[hd++];
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (!(--ind[v])) {
q[++tl] = v;
}
}
}
for (int i = 1; i <= ntot; ++i) {
if (ind[i]) {
puts("No");
return;
}
}
puts("Yes");
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
鲜花：
调了一下午。