#include "bits/stdc++.h"
using namespace std;
#define ll long long
const ll N = 1e6 + 5;
vector<ll> v[N],g[N];
ll n,m,depth[N],vis[N],S[N],T[N],tin[N],ti,par[N],sub[N],tail[N],p[N],inv[N],xd[N],ptr;
array<ll,2> ar[N];
bool ok = 1;
inline void Add_Edge(ll a,ll b){
if(a != b) g[a].push_back(b);
}
void dfs(ll c,ll p){
par[c] = p;
for(ll x : v[c]){
if(x == p) continue;
depth[x] = depth[c] + 1;
dfs(x, c);
}
}
void Prep(ll c,ll p){
sub[c] = 1;
for(ll x : v[c]){
if(x == p) continue;
Prep(x, c);
sub[c] += sub[x];
}
}
void HLD(ll c,ll p,ll h){
tail[c] = h, xd[c] = ti;
tin[ti++] = c;
ll ne = -1;
for(ll u : v[c]){
if(u == p) continue;
if(ne == -1 || sub[u] > sub[ne]) ne = u;
}
if(ne != -1) HLD(ne, c, h);
for(ll u : v[c]){
if(u == p || u == ne) continue;
HLD(u, c, u);
}
}
void Create(ll rt,ll l,ll r){
p[rt] = ++ptr;
if(l == r){
if(S[tin[l]] != -1){
Add_Edge(p[rt], S[tin[l]]);
}
return;
}
ll mid = (l + r) / 2;
Create(rt * 2, l, mid), Create(rt * 2 + 1, mid + 1, r);
Add_Edge(p[rt], p[rt * 2]);
Add_Edge(p[rt], p[rt * 2 + 1]);
}
void Create2(ll rt,ll l,ll r){
inv[rt] = ++ptr;
if(l == r){
if(T[tin[l]] != -1){
Add_Edge(T[tin[l]], inv[rt]);
}
return;
}
ll mid = (l + r) / 2;
Create2(rt * 2, l, mid), Create2(rt * 2 + 1, mid + 1, r);
Add_Edge(inv[rt * 2], inv[rt]);
Add_Edge(inv[rt * 2 + 1], inv[rt]);
}
void Add(ll rt,ll l,ll r,ll gl,ll gr,ll nd,bool gg){
if(r < gl || l > gr) return;
if(l >= gl && r <= gr){
if(gg){
Add_Edge(nd, p[rt]);
}
else{
Add_Edge(inv[rt], nd);
}
return;
}
ll mid = (l + r) / 2;
Add(rt * 2, l, mid, gl, gr, nd, gg), Add(rt * 2 + 1, mid + 1, r, gl, gr, nd, gg);
}
void Find(ll c){
if(vis[c] == 2 || !ok) return;
if(vis[c] == 1){
ok = 0;
return;
}
vis[c] = 1;
for(ll u : g[c]) Find(u);
vis[c] = 2;
}
inline void Hm(ll l,ll r,ll nd){
ll ln = xd[ar[nd][0]];
if(ln >= l && ln <= r){
if(l < ln) Add(1,1,n,l,ln-1,nd,1);
if(ln < r) Add(1,1,n,ln+1,r,nd,1);
}
else Add(1,1,n,l,r,nd,1);
ln = xd[ar[nd][1]];
if(ln >= l && ln <= r){
if(l < ln) Add(1,1,n,l,ln-1,nd,0);
if(ln < r) Add(1,1,n,ln+1,r,nd,0);
}
else Add(1,1,n,l,r,nd,0);
}
void Solve(){
cin >> n;
ok = ti = 1;
for(ll i=0;i<=min(N-1,8*n);i++){
vis[i] = sub[i] = 0;
v[i].clear(),g[i].clear();
S[i] = T[i] = -1;
}
for(ll i=1;i<n;i++){
ll a,b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1, 1);
Prep(1, 1);
HLD(1, 1, 1);
cin >> m;
ptr = m;
for(ll i=1;i<=m;i++){
cin >> ar[i][0] >> ar[i][1];
S[ar[i][0]] = i;
T[ar[i][1]] = i;
}
Create(1, 1, n);
Create2(1, 1, n);
for(ll i=1;i<=m;i++){
ll a = ar[i][0], b = ar[i][1];
for(;tail[a]!=tail[b]; b = par[tail[b]]){
if(depth[tail[a]] > depth[tail[b]]) swap(a, b);
Hm(xd[tail[b]], xd[b], i);
}
if(depth[a] > depth[b]) swap(a, b);
Hm(xd[a], xd[b], i);
}
for(ll i=1;i<=ptr;i++){
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()),g[i].end());
}
for(ll i=1;i<=ptr;i++) Find(i);
if(ok) cout << "Yes\n";
else cout << "No\n";
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
ll q=1;
cin >> q;
for (int i = 0; i < q; i++) {
Solve();
}
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... |