#include <bits/stdc++.h>
using namespace std;
unordered_set<int>sfin;
unordered_set<int>tfin;
void dfs(int st, vector<int>g[], int p, int d, int dep[], int par[]){
par[st]=p;
dep[st]=d;
for(int i : g[st]){
if(i==p)
continue;
dfs(i,g,st,d+1,dep,par);
}
}
void finder(int s, int t, int revs[], int revt[], int dep[], int par[]){
sfin.clear();
tfin.clear();
while(s!=t){
if(dep[s]<dep[t]){
swap(s,t);
}
//s is deeper now
sfin.insert(revs[s]);
tfin.insert(revt[s]);
s=par[s];
}
sfin.insert(revs[s]);
tfin.insert(revt[s]);
}
bool cyc;
void checkcyc(int st, vector<int>g[], int vis[]){
vis[st]=1;
for(int i : g[st]){
if(vis[i]==1){
cyc=1;
}
if(vis[i])
continue;
checkcyc(i,g,vis);
}
vis[st]=2;
}
void solve(){
int n;
cin >> n;
vector<int>g[n];
for(int i = 0;i<n-1;i++){
int a,b;
cin >> a >> b;
a--;b--;
g[a].push_back(b);
g[b].push_back(a);
}
int m;
cin >> m;
int s[m],t[m];
int revs[n],revt[n];
fill(revs,revs+n,-1);
fill(revt,revt+n,-1);
for(int i = 0;i<m;i++){
cin >> s[i] >> t[i];
s[i]--;
t[i]--;
revs[s[i]]=i;
revt[t[i]]=i;
}
//line case.
set<array<int,2>>forw;
set<array<int,2>>bac;
for(int i = 0;i<m;i++){
if(s[i]<t[i]){
forw.insert({s[i],t[i]});
}
else{
bac.insert({-s[i],-t[i]});
}
}
int las = -1;
for(array<int,2>a:forw){
if(a[1]<las){
cout << "No\n";
return;
}
las=a[1];
}
las=-1e9;
for(array<int,2>a:bac){
if(a[1]<las){
cout << "No\n";
return;
}
las=a[1];
}
for(int i = 0;i<m;i++){
if(s[i]<t[i]){
continue;
}
swap(s[i],t[i]);
//check for intersections.
auto it = forw.upper_bound({s[i],1000000000});
if(it!=forw.end()){
if((*it)[0]<=t[i]){
cout << "No\n";
return;
}
}
if(it!=forw.begin()){
it--;
if((*it)[1]>=s[i]){
cout << "No\n";
return;
}
}
}
cout << "Yes\n";
return;
unordered_set<int>spath[m];
unordered_set<int>tpath[m];
int dep[n];
int par[n];
dfs(0,g,-1,0,dep,par);
for(int i = 0;i<m;i++){
finder(s[i],t[i],revs,revt,dep,par);
for(int j : sfin){
spath[i].insert(j);
}
for(int j : tfin){
tpath[i].insert(j);
}
}
vector<int>g2[m];
for(int i = 0;i<m;i++){
for(int j : spath[i]){
if(j==-1||j==i){
continue;
}
g2[j].push_back(i);
}
for(int j : tpath[i]){
if(j==-1||j==i){
continue;
}
g2[i].push_back(j);
}
}
//now check for cycle.
cyc=0;
int vis[m];
fill(vis,vis+m,0);
for(int i = 0;i<m;i++){
if(vis[i]==0){
checkcyc(i,g2,vis);
}
}
for(bool i : vis){
if(!i){
cyc=1;
}
}
if(cyc){
cout << "No\n";
}
else{
cout << "Yes\n";
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
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... |