#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int N;
cin >> N;
vector<vector<int>> graph(N);
for (int i = 0; i < N - 1; i++) {
int A, B;
cin >> A >> B;
--A, --B;
graph[A].push_back(B);
graph[B].push_back(A);
}
int M;
cin >> M;
vector<int> S(M), T(M);
for (int i = 0; i < M; i++) {
cin >> S[i] >> T[i];
--S[i], --T[i];
}
vector<int> parent(N), sizes(N);
auto DFS = [&](auto&& self, int u, int par) -> void {
if (par != -1) {
graph[u].erase(find(graph[u].begin(), graph[u].end(), par));
}
parent[u] = par;
sizes[u] = 1;
for (int &v : graph[u]) {
self(self, v, u);
sizes[u] += sizes[v];
if (sizes[v] > sizes[graph[u][0]]) {
swap(v, graph[u][0]);
}
}
};
vector<int> tin(N), tout(N), head(N);
int tin_cur = 0;
auto BuildHLD = [&](auto&& self, int u) -> void {
tin[u] = tin_cur++;
for (int v : graph[u]) {
head[v] = (v == graph[u][0] ? head[u] : v);
self(self, v);
}
tout[u] = tin_cur;
};
DFS(DFS, 0, -1);
BuildHLD(BuildHLD, 0);
vector<vector<int>> seg(4 * N + M);
for (int i = N - 1; i > 0; i--) {
seg[i * 2].push_back(i);
seg[i * 2 + 1].push_back(i);
seg[2 * N + i].push_back(2 * N + i * 2);
seg[2 * N + i].push_back(2 * N + i * 2 + 1);
}
for (int i = 0; i < M; i++) {
seg[4 * N + i].push_back(N + S[i]);
seg[3 * N + T[i]].push_back(4 * N + i);
}
auto AddEdge = [&](int u, int l, int r) {
for (int side = 0; side < 2; side++) {
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
auto Add = [&](int v) {
if (side == 0) {
seg[2 * N * side + v].push_back(4 * N + u);
} else {
seg[4 * N + u].push_back(2 * N * side + v);
}
};
if (l & 1) {
Add(l++);
}
if (r & 1) {
Add(--r);
}
}
}
};
auto IsAncestor = [&](int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
};
for (int i = 0; i < M; i++) {
int s = S[i], t = T[i], delta = 0;
while (!IsAncestor(head[s], t)) {
AddEdge(i, tin[head[s]], tin[s] + delta);
s = parent[head[s]];
delta = 1;
}
while (!IsAncestor(head[t], s)) {
AddEdge(i, tin[head[t]], tin[t] + 1);
t = parent[head[t]];
}
if (IsAncestor(s, t)) {
AddEdge(i, tin[s] + !delta, tin[t] + 1);
} else {
AddEdge(i, tin[t], tin[s] + delta);
}
}
vector<int> color(4 * N + M);
auto FindCycle = [&](auto&& self, int u) -> bool {
color[u] = 2;
for (int v : seg[u]) {
if (color[v] == 2) {
return true;
}
if (!color[v] && self(self, v)) {
return true;
}
}
color[u] = 1;
return false;
};
bool good = true;
for (int i = 0; i < 4 * N + M; i++) {
if (!color[i] && FindCycle(FindCycle, i)) {
good = false;
}
}
cout << (good ? "Yes\n" : "No\n");
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |