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>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
const int N = 1.2e5;
vector<int> g[N + 1], G[9 * N];
int s[N + 1], t[N + 1], sz[N + 1], h[N + 1], p[N + 1], d[N + 1], head[N + 1], pos[N + 1], a[N + 1], b[N + 1], k, m, n;
void build1(int v, int tl, int tr){
if (tl == tr){
if (a[tl]) G[v + m].pb(a[tl]);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
build1(vv, tl, tm);
build1(vv + 1, tm + 1, tr);
G[v + m].pb(vv + m);
G[v + m].pb(vv + m + 1);
}
void build2(int v, int tl, int tr){
if (tl == tr){
if (b[tl]) G[b[tl]].pb(v + k);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
build2(vv, tl, tm);
build2(vv + 1, tm + 1, tr);
G[vv + k].pb(v + k);
G[vv + k + 1].pb(v + k);
}
void add1(int v, int tl, int tr, int& l, int& r, int& u){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
G[u].pb(v + m);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
add1(vv, tl, tm, l, r, u);
add1(vv + 1, tm + 1, tr, l, r, u);
}
void add1(int u, int l, int r){
if (l > r) return;
add1(1, 1, n, l, r, u);
}
void add2(int v, int tl, int tr, int& l, int& r, int& u){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
G[v + k].pb(u);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
add2(vv, tl, tm, l, r, u);
add2(vv + 1, tm + 1, tr, l, r, u);
}
void add2(int u, int l, int r){
if (l > r) return;
add2(1, 1, n, l, r, u);
}
bool used[9 * N], seen[9 * N];
bool dfs(int v){
used[v] = seen[v] = 1;
for (int i: G[v]){
if (used[i]){
if (seen[i]){
return 0;
}
continue;
}
if (!dfs(i)) return 0;
}
seen[v] = 0;
return 1;
}
bool check(){
int nn = 9 * n;
for (int i = 1; i < nn; i++) used[i] = seen[i] = 0;
for (int i = 1; i <= nn; i++){
if (!used[i]){
if (!dfs(i)){
return 0;
}
}
}
return 1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt; cin>>tt;
while (tt--){
cin>>n;
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i < n; i++){
int x, y; cin>>x>>y;
g[x].pb(y);
g[y].pb(x);
}
cin>>m;
for (int i = 1; i <= m; i++){
cin>>s[i]>>t[i];
}
function<void(int, int)> fill = [&](int v, int pr){
p[v] = pr;
sz[v] = 1;
for (int i: g[v]){
if (i == pr) continue;
d[i] = d[v] + 1;
fill(i, v);
if (sz[i] > sz[h[v]]){
h[v] = i;
}
sz[v] += sz[i];
}
};
fill(1, 0);
for (int i = 1; i <= n; i++) pos[i] = 0;
int timer = 0;
function<void(int, int)> fill_hld = [&](int v, int k){
head[v] = k;
pos[v] = ++timer;
if (!h[v]) return;
fill_hld(h[v], k);
for (int i: g[v]){
if (pos[i]) continue;
fill_hld(i, i);
}
};
fill_hld(1, 1);
for (int i = 1; i <= n; i++) a[i] = b[i] = 0;
for (int i = 1; i <= m; i++){
a[pos[s[i]]] = i;
b[pos[t[i]]] = i;
}
for (int i = 1; i < 9 * n; i++) G[i].clear();
k = m + 4 * n;
build1(1, 1, n);
build2(1, 1, n);
for (int i = 1; i <= m; i++){
int x = s[i], y = t[i];
while (head[x] != head[y]){
if (d[head[x]] > d[head[y]]){
swap(x, y);
}
add1(i, pos[head[y]] + (head[y] == s[i]), pos[y] - (y == s[i]));
add2(i, pos[head[y]] + (head[y] == t[i]), pos[y] - (y == t[i]));
y = p[head[y]];
}
if (d[x] > d[y]) swap(x, y);
add1(i, pos[x] + (x == s[i]), pos[y] - (y == s[i]));
add2(i, pos[x] + (x == t[i]), pos[y] - (y == t[i]));
}
cout<<((check()) ? "Yes" : "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... |