#include <bits/stdc++.h>
using namespace std;
const int maxn = 120005;
vector<int> g[maxn];
int n, par[maxn], hd[maxn], sz[maxn], dep[maxn], dfn[maxn], seq[maxn], best[maxn], dft, memtp, tg[10 * maxn], tp, indeg[10 * maxn];
pair<int, int> walk[maxn], mem[100 * maxn];
struct node {
int up, dwn;
} seg[maxn << 2];
void adde(int u, int v) {
mem[++memtp] = pair<int, int>(tg[u], v);
tg[u] = memtp;
++indeg[v];
}
void build(int l, int r, int rt) {
if (l == r) {
seg[rt].up = l;
seg[rt].dwn = l + n;
return;
}
seg[rt].up = ++tp;
indeg[tp] = 0;
tg[tp] = 0;
seg[rt].dwn = ++tp;
indeg[tp] = 0;
tg[tp] = 0;
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
adde(seg[rt << 1].up, seg[rt].up);
adde(seg[rt << 1 | 1].up, seg[rt].up);
adde(seg[rt].dwn, seg[rt << 1].dwn);
adde(seg[rt].dwn, seg[rt << 1 | 1].dwn);
}
void modify(int L, int R, int l, int r, int rt, int up, int idx) {
if (L <= l && R >= r) {
if (up) adde(seg[rt].up, idx);
else adde(idx, seg[rt].dwn);
return;
}
int mid = (l + r) >> 1;
if (L <= mid) modify(L, R, l, mid, rt << 1, up, idx);
if (R > mid) modify(L, R, mid + 1, r, rt << 1 | 1, up, idx);
}
void dfs1(int u, int f) {
par[u] = f;
sz[u] = 1;
best[u] = 0;
for (auto v : g[u]) if (v != f) {
dep[v] = dep[u] + 1;
dfs1(v, u);
sz[u] += sz[v];
if (sz[best[u]] < sz[i]) best[u] = v;
}
}
void dfs2(int u, int h) {
hd[u] = h;
dfn[u] = ++dft;
seg[dft] = u;
if (best[u]) dfs2(best[u], h);
for (auto v : g[u]) if (v != par[u] && v != best[u]) dfs2(v, v);
}
void pathadd(int u, int v, int up, int idx) {
int ban = v;
while (hd[u] != hd[v]) {
if (dep[hd[u]] < dep[hd[v]]) swap(u, v);
if (u != ban) modify(dfn[hd[u]], dfn[u], 1, n, 1, up, idx);
else if (dfn[hd[u]] < dfn[u]) modify(dfn[hd[u]], dfn[u] - 1, 1, n, 1, up, idx);
u = par[hd[u]];
}
if (dfn[u] > dfn[v]) swap(u, v);
if (u != ban && v != ban) modify(dfn[u], dfn[v], 1, n, 1, up, idx);
else if (u == ban && dfn[u] < dfn[v]) modify(dfn[u] + 1, dfn[v], 1, n, 1, up, idx);
else if (v == ban && dfn[u] < dfn[v]) modify(dfn[u], dfn[v] - 1, 1, n, 1, up, idx);
}
bool solve() {
memtp = 0;
int m;
cin >> n;
tp = n * 2;
for (int i = 1; i <= n; i++) {
g[i].clear();
indeg[i] = tg[i] = indeg[i + n] = tg[i + n] = 0;
}
build(1, n, 1);
for (int i = 1, a, b; i < n; i++) {
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dft = 0;
dfs1(1, 1);
dfs2(1, 1);
cin >> m;
for (int i = 1; i <= m; i++) {
indeg[tp + i] = tg[tp + i] = 0;
cin >> walk[i].first >> walk[i].second;
}
for (int i = 1; i <= m; i++) {
adde(tp + i, dfn[walk[i].first]);
adde(dfn[walk[i].second] + n, tp + i);
}
for (int i = 1; i <= m; i++) {
int u = walk[i].first, v = walk[i].second;
pathadd(u, v, 0, tp + i);
pathadd(v, u, 1, tp + i);
}
tp += m;
queue<int> q;
for (int i = 1; i <= tp; i++) if (!indeg[i]) q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
while (tg[u] != 0) {
if (!--indeg[mem[tg[u]].second]) q.push(mem[tg[u]].second);
tg[u] = mem[tg[u]].first;
}
}
for (int i = 1; i <= tp; i++) if (indeg[i]) return 0;
return 1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
if (solve()) cout << "Yes" << '\n';
else cout << "No" << '\n';
}
}
Compilation message
jail.cpp: In function 'void dfs1(int, int)':
jail.cpp:60:24: error: 'i' was not declared in this scope
60 | if (sz[best[u]] < sz[i]) best[u] = v;
| ^
jail.cpp: In function 'void dfs2(int, int)':
jail.cpp:67:13: error: no match for 'operator=' (operand types are 'node' and 'int')
67 | seg[dft] = u;
| ^
jail.cpp:10:8: note: candidate: 'constexpr node& node::operator=(const node&)'
10 | struct node {
| ^~~~
jail.cpp:10:8: note: no known conversion for argument 1 from 'int' to 'const node&'
jail.cpp:10:8: note: candidate: 'constexpr node& node::operator=(node&&)'
jail.cpp:10:8: note: no known conversion for argument 1 from 'int' to 'node&&'
