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>
using namespace std;
// Input & Graph
int N, A[200009], B[200009];
int M, S[200009], T[200009];
int SVal[200009], TVal[200009];
int Sidx[200009][20];
int Tidx[200009][20];
vector<int> G[200009];
vector<int> H[9000009];
// Others
int NumVertices;
int parent[200009][20], dist[200009];
int indeg[9000009];
vector<int> tmp, Path;
void AllInit(int N, int M, int Verts) {
for (int i = 0; i < N; i++) G[i].clear();
for (int i = 0; i < Verts; i++) H[i].clear();
NumVertices = 0;
}
void dfs_init(int pos, int par, int dep) {
dist[pos] = dep;
for (int to : G[pos]) {
if (to == par) continue;
parent[to][0] = pos;
dfs_init(to, pos, dep + 1);
}
}
int prevs(int pos, int x) {
for (int i = 19; i >= 0; i--) {
if (x >= (1 << i)) { pos = parent[pos][i]; x -= (1 << i); }
}
return pos;
}
int GetLCA(int u, int v) {
if (dist[u] > dist[v]) swap(u, v);
v = prevs(v, dist[v] - dist[u]);
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (parent[u][i] == parent[v][i]) continue;
u = parent[u][i];
v = parent[v][i];
}
return parent[u][0];
}
bool TopologicalSort() {
for (int i = 0; i < NumVertices; i++) indeg[i] = 0;
for (int i = 0; i < NumVertices; i++) {
for (int j : H[i]) indeg[j] += 1;
}
queue<int> Q;
for (int i = 0; i < NumVertices; i++) {
if (indeg[i] == 0) Q.push(i);
}
while (!Q.empty()) {
int pos = Q.front(); Q.pop();
for (int to : H[pos]) {
indeg[to] -= 1;
if (indeg[to] == 0) Q.push(to);
}
}
for (int i = 0; i < NumVertices; i++) {
if (indeg[i] != 0) return false;
}
return true;
}
void AddS(int pos, int x, int base) {
for (int i = 19; i >= 0; i--) {
if (x < (1 << i)) continue;
H[Sidx[pos][i]].push_back(base);
x -= (1 << i);
pos = parent[pos][i];
}
}
void AddT(int pos, int x, int base) {
for (int i = 19; i >= 0; i--) {
if (x < (1 << i)) continue;
H[base].push_back(Tidx[pos][i]);
x -= (1 << i);
pos = parent[pos][i];
}
}
bool GetAnswer(int NN, vector<int> AA, vector<int> BB, int MM, vector<int> SS, vector<int> TT) {
AllInit(N, M, NumVertices);
N = NN;
for (int i = 0; i < N - 1; i++) A[i] = AA[i] - 1;
for (int i = 0; i < N - 1; i++) B[i] = BB[i] - 1;
M = MM;
for (int i = 0; i < M; i++) S[i] = SS[i] - 1;
for (int i = 0; i < M; i++) T[i] = TT[i] - 1;
// Step #1. Obvious Case
for (int i = 0; i < N; i++) SVal[i] = -1;
for (int i = 0; i < N; i++) TVal[i] = -1;
for (int i = 0; i < M; i++) {
if (SVal[S[i]] != -1) return false;
else SVal[S[i]] = i;
if (TVal[T[i]] != -1) return false;
else TVal[T[i]] = i;
}
// Step #2. Make Graph
for (int i = 0; i < N - 1; i++) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
// Step #3. Get LCA
dfs_init(0, -1, 0);
parent[0][0] = -1;
for (int i = 0; i < 19; i++) {
for (int j = 0; j < N; j++) {
if (parent[j][i] == -1) parent[j][i + 1] = -1;
else parent[j][i + 1] = parent[parent[j][i]][i];
}
}
// Step #4. Init Sparse Table
NumVertices = M;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < N; j++) { NumVertices += 1; Sidx[j][i] = NumVertices; }
}
for (int i = 0; i < 20; i++) {
for (int j = 0; j < N; j++) { NumVertices += 1; Tidx[j][i] = NumVertices; }
}
for (int i = 0; i < 19; i++) {
for (int j = 0; j < N; j++) {
int idx1 = Sidx[j][i + 1];
int idx2 = Tidx[j][i + 1];
int pars = parent[j][i];
H[Sidx[j][i]].push_back(idx1);
H[idx2].push_back(Tidx[j][i]);
if (pars != -1) {
H[Sidx[pars][i]].push_back(idx1);
H[idx2].push_back(Tidx[pars][i]);
}
}
}
for (int i = 0; i < N; i++) {
int idx1 = Sidx[i][0];
int idx2 = Tidx[i][0];
if (SVal[i] != -1) H[SVal[i]].push_back(idx1);
if (TVal[i] != -1) H[idx2].push_back(TVal[i]);
}
// Step #5. Add Edges
for (int i = 0; i < M; i++) {
int LCA = GetLCA(S[i], T[i]);
int LengthS = dist[S[i]] - dist[LCA];
int LengthT = dist[T[i]] - dist[LCA];
if (LengthS >= 2) {
AddS(parent[S[i]][0], LengthS - 1, i);
AddT(parent[S[i]][0], LengthS - 1, i);
}
if (LengthT >= 2) {
AddS(parent[T[i]][0], LengthT - 1, i);
AddT(parent[T[i]][0], LengthT - 1, i);
}
vector<int> Cand = {S[i], T[i], LCA};
for (int j : Cand) {
if (SVal[j] != i && SVal[j] != -1) H[SVal[j]].push_back(i);
if (TVal[j] != i && TVal[j] != -1) H[i].push_back(TVal[j]);
}
}
// Step #6. Topological Sort
bool ret = TopologicalSort();
return ret;
}
int main() {
int Q;
cin >> Q;
for (int testcase = 1; testcase <= Q; testcase++) {
// Input
int NN, MM;
cin >> NN;
vector<int> AA(NN - 1, 0), BB(NN - 1, 0);
for (int i = 0; i < NN - 1; i++) cin >> AA[i] >> BB[i];
cin >> MM;
vector<int> SS(MM, 0), TT(MM, 0);
for (int i = 0; i < MM; i++) cin >> SS[i] >> TT[i];
// Output
bool FinalAns = GetAnswer(NN, AA, BB, MM, SS, TT);
if (FinalAns == true) cout << "Yes" << endl;
if (FinalAns == false) cout << "No" << endl;
}
return 0;
}
# | 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... |