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