This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define endl '\n'
const int N = 2e5+23, lg = 18;
ll Mod = 1e9+7;
//ll Mod = 998244353;
inline ll MOD(ll a, ll mod=Mod) {
a%=mod; (a<0)&&(a+=mod); return a;
}
inline ll max(ll a, ll b) {return (a>b ? a : b);}
inline ll min(ll a, ll b) {return (a<b ? a : b);}
inline ll abso(ll a) {return (a<0?-a:a);}
inline ll poww(ll a, ll b, ll mod=Mod) {
ll ans = 1;
a=MOD(a, mod);
while (b) {
if (b & 1) ans = MOD(ans*a, mod);
b >>= 1;
a = MOD(a*a, mod);
}
return ans;
}
struct Node {
int deg;
vector<int> adj;
Node() {
deg=0;
}
} node[N*20];
int q, n, m, cnt, h[N], par[lg][N], s[N], t[N], rs[N], rt[N];
int fakes[lg][N], faket[lg][N];
vector<int> tree[N];
void add(int v, int u) {
if(v==0 || u==0 || v==u) return;
node[v].adj.pb(u);
node[u].deg++;
}
void init(int v, int p=0) {
par[0][v]=p, h[v]=h[p]+1;
for(int i=1; i<lg; i++) {
par[i][v] = par[i-1][par[i-1][v]];
}
for(int i=0; i<lg; i++) {
fakes[i][v] = ++cnt;
faket[i][v] = ++cnt;
}
int tmp = v;
add(faket[0][v], rt[tmp]);
tmp = par[0][v];
add(faket[0][v], rt[tmp]);
tmp = v;
add(rs[tmp], fakes[0][v]);
tmp = par[0][v];
add(rs[tmp], fakes[0][v]);
for(int i=1; i<lg; i++) {
add(faket[i][v], faket[i-1][v]);
add(faket[i][v], faket[i-1][par[i-1][v]]);
add(fakes[i-1][v], fakes[i][v]);
add(fakes[i-1][par[i-1][v]], fakes[i][v]);
}
for(int u : tree[v]) {
if(u == p) continue;
init(u, v);
}
}
int getPar(int v, int dist) {
for(int i=0; i<lg; i++) {
if((dist>>i)%2) {
v = par[i][v];
}
}
return v;
}
int LCA(int v, int u) {
if(h[u] < h[v]) swap(v,u);
u = getPar(u, h[u]-h[v]);
if(v == u) return v;
for(int i=lg-1; i>=0; i--) {
if(par[i][v] != par[i][u]) {
v=par[i][v], u=par[i][u];
}
}
return par[0][v];
}
void addPaths(int cnd, int v, int dist) {
if(dist<0 || cnd==0 || v==0) return;
//cout<<"addPath : "<<cnd<<' '<<v<<' '<<dist<<endl;
if(dist == 0) {
//add(cnd, rt[v]);
add(rs[v], cnd);
return;
}
for(int i=0; i<lg; i++) {
if((dist>>i)%2==1) {
//cout<<"edge : "<<cnd<<" ===> ("<<i<<", "<<v<<")\n";
//add(cnd, faket[i][v]);
//cout<<"edge : "<<cnd<<" <=== ("<<i<<", "<<v<<")\n";
add(fakes[i][v], cnd);
v = par[i][v];
}
}
return;
}
void addPatht(int cnd, int v, int dist) {
if(dist<0 || cnd==0 || v==0) return;
//cout<<"addPath : "<<cnd<<' '<<v<<' '<<dist<<endl;
if(dist == 0) {
add(cnd, rt[v]);
return;
}
for(int i=0; i<lg; i++) {
if((dist>>i)%2==1) {
//cout<<"edge : "<<cnd<<" ===> ("<<i<<", "<<v<<")\n";
add(cnd, faket[i][v]);
//cout<<"edge : "<<cnd<<" <=== ("<<i<<", "<<v<<")\n";
//add(fakes[i][v], cnd);
v = par[i][v];
}
}
return;
}
void solve() {
cin>>n;
for(int v,u,i=1; i<n; i++) {
cin>>v>>u;
tree[v].pb(u); tree[u].pb(v);
}
cin>>m;
for(int i=1; i<=m; i++) {
cin>>s[i]>>t[i];
rs[s[i]] = i;
rt[t[i]] = i;
}
cnt = m;
init(1);
for(int i=1; i<=m; i++) {
int lca = LCA(s[i], t[i]);
//int ff = (s[i]==lca || t[i]==lca);
addPaths(i, par[0][s[i]], h[par[0][s[i]]] - h[lca]);
addPatht(i, s[i], h[s[i]] - h[lca] - (t[i]==lca));
addPaths(i, t[i], h[t[i]] - h[lca] - (s[i]==lca));
addPatht(i, par[0][t[i]], h[par[0][t[i]]] - h[lca]);
}
int cnt2=0;
queue<int> q;
for(int i=1; i<=cnt; i++) {
if(node[i].deg == 0) q.push(i);
}
while(size(q)) {
int v = q.front();
q.pop();
cnt2 ++;
for(int u : node[v].adj) {
node[u].deg--;
if(node[u].deg==0) {
q.push(u);
}
}
}
//fuck(cnt); fuck(cnt2);
if(cnt2 == cnt) cout<<"Yes\n";
else cout<<"No\n";
}
/*
node[N*20];
int q, n, m, cnt, h[N], par[lg][N], s[N], t[N], rs[N], rt[N];
int fakes[lg][N], faket[lg][N];
vector<int> tree[N];
*/
void reset() {
for(int i=0; i<=n+2; i++) {
h[i]=s[i]=t[i]=rs[i]=rt[i]=0;
for(int j=0; j<lg; j++) {
fakes[j][i]=faket[j][i]=0;
}
while(size(tree[i])) tree[i].pop_back();
}
for(int i=0; i<=cnt; i++) {
node[i].deg=0;
while(size(node[i].adj)) node[i].adj.pop_back();
}
}
int main () {
ios_base::sync_with_stdio(false), cin.tie(0);
cin>>q;
while(q--) {
solve();
reset();
}
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... |