This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int SZ = 1 << 17;
vector<int> TG[SZ], G[SZ], G2[SZ << 3];
pii E[SZ];
int D[SZ], P[17][SZ], Z[SZ], R[SZ], in[SZ], out[SZ], id[SZ << 3], dn;
void MakeG(int cur, int prev) {
P[0][cur] = prev;
D[cur] = D[prev] + 1;
for (int next : TG[cur]) {
if (next == prev) continue;
G[cur].push_back(next);
MakeG(next, cur);
}
}
int DFS(int cur) {
int& ret = Z[cur] = 1;
for (int i = 0; i < G[cur].size(); ++i) {
int next = G[cur][i];
ret += DFS(next);
if (Z[next] > Z[G[cur][0]]) swap(G[cur][0], G[cur][i]);
}
return ret;
}
void DFS2(int cur, int top) {
in[cur] = ++dn;
R[cur] = top;
for (int i = 0; i < G[cur].size(); ++i) {
int next = G[cur][i];
DFS2(next, (i == 0 ? top : next));
}
out[cur] = dn;
}
int LCA(int a, int b) {
while (R[a] != R[b]) {
if (D[R[a]] > D[R[b]]) swap(a, b);
b = P[0][R[b]];
}
return (D[a] > D[b] ? b : a);
}
void Segment(int L, int R, vector<int>& node, int sL, int sR, int n = 1) {
if (R < sL || sR < L) return;
if (L <= sL && sR <= R) {
node.push_back(n);
return;
}
int mid = (sL + sR) >> 1;
Segment(L, R, node, sL, mid, n * 2);
Segment(L, R, node, mid + 1, sR, n * 2 + 1);
}
vector<int> Decompose(int s, int e, int CZ) {
vector<pii> seg;
vector<int> ret;
int c = LCA(s, e);
if (c == s) {
int t = e, d = D[e] - D[s] - 1;
for (int i = 16; i >= 0; --i) if (d & (1 << i)) t = P[i][t];
s = t;
}
else s = P[0][s];
while (R[s] != R[e]) {
if (D[R[s]] > D[R[e]]) swap(s, e);
seg.emplace_back(in[R[e]], in[e]);
e = P[0][R[e]];
}
if (D[s] > D[e]) swap(s, e);
seg.emplace_back(in[s], in[e]);
for (auto [a, b] : seg) Segment(a, b, ret, 1, CZ);
return ret;
}
int main() {
int test;
cin >> test;
while (test--) {
int N, M, no = 0, CZ = 1;
cin >> N;
for (int i = 1; i < N; ++i) {
int a, b;
cin >> a >> b;
TG[a].push_back(b);
TG[b].push_back(a);
}
cin >> M;
for (int i = 1; i <= M; ++i) cin >> E[i].first >> E[i].second;
while (CZ < N) CZ <<= 1;
dn = 0;
MakeG(1, 1);
DFS(1);
DFS2(1, 1);
for (int i = 1; i < 17; ++i) for (int n = 1; n <= N; ++n) P[i][n] = P[i - 1][P[i - 1][n]];
memset(id, 0, sizeof(id));
for (int i = 1; i <= M; ++i) {
auto [s, e] = E[i];
vector<int> from = Decompose(s, e, CZ);
vector<int> to = Decompose(e, s, CZ);
for (int& n : to) n += CZ * 2;
int cur = CZ * 4 + i;
for (int n : from) G2[n].push_back(cur), id[cur]++;
for (int n : to) G2[cur].push_back(n), id[n]++;
G2[cur].push_back(in[s] + CZ - 1), id[in[s] + CZ - 1]++;
G2[in[e] + CZ * 3 - 1].push_back(cur), id[cur]++;
}
for (int i = 1; i < CZ; ++i) {
G2[i * 2].push_back(i), id[i]++;
G2[i * 2 + 1].push_back(i), id[i]++;
int t = CZ * 2;
G2[t + i].push_back(t + i * 2), id[t + i * 2]++;
G2[t + i].push_back(t + i * 2 + 1), id[t + i * 2 + 1]++;
}
queue<int> Q;
int cnt = CZ * 4 + M;
for (int i = 1; i <= CZ * 4 + M; ++i) {
if (!id[i]) Q.push(i);
}
while (!Q.empty()) {
int cur = Q.front(); Q.pop();
cnt--;
for (int next : G2[cur]) {
if (!--id[next]) Q.push(next);
}
}
cout << (cnt ? "No" : "Yes") << '\n';
for (int i = 1; i <= N; ++i) {
G[i].clear();
TG[i].clear();
}
for (int i = 0; i < (CZ * 8); ++i) G2[i].clear();
}
return 0;
}
Compilation message (stderr)
jail.cpp: In function 'int DFS(int)':
jail.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int i = 0; i < G[cur].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
jail.cpp: In function 'void DFS2(int, int)':
jail.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = 0; i < G[cur].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:86:19: warning: unused variable 'no' [-Wunused-variable]
86 | int N, M, no = 0, CZ = 1;
| ^~
# | 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... |