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>
using namespace std;
const int N=120005;
const int K=18;
int n,m;
vector<vector<int>> adj;
vector<vector<int>> g;
vector<vector<int>> jump(K,vector<int>(N));
vector<int> deep(N);
vector<int> s1;
vector<int> t1;
void dfs(int k,int pa){
jump[0][k]=pa;
for(int i=1;i<K;i++){
jump[i][k]=jump[i-1][jump[i-1][k]];
}
for(int j:adj[k]){
if(j==pa){
continue;
}
deep[j]=deep[k]+1;
dfs(j,k);
}
}
int lca(int a,int b){
if(deep[a]<deep[b]){
swap(a,b);
}
int d=deep[a]-deep[b];
for(int i=0;i<K;i++){
if((1<<i)&d){
a=jump[i][a];
}
}
if(a==b){
return b;
}
for(int i=K-1;i>=0;i--){
if(jump[i][a]!=jump[i][b]){
a=jump[i][a];
b=jump[i][b];
}
}
return jump[0][a];
}
int num1(int a,int b){
return m+b*n+a;
}
int num2(int a,int b){
return m+(b+K)*n+a;
}
void add1(int from,int to,int dis){
if(dis==-1){
return;
}
for(int i=0;i<K;i++){
if(dis&(1<<i)){
g[from].push_back(num1(to,i));
to=jump[i][to];
}
}
}
void add2(int to,int from,int dis){
if(dis==-1){
return;
}
for(int i=0;i<K;i++){
if(dis&(1<<i)){
g[num2(from,i)].push_back(to);
from=jump[i][from];
}
}
}
void solve(){
adj.clear();
g.clear();
s1.resize(0);
t1.resize(0);
cin>>n;
adj.resize(n);
s1.resize(n,-1);
t1.resize(n,-1);
for(int i=1;i<n;i++){
int a,b;cin>>a>>b;a--;b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0,0);
cin>>m;
int N=num2(n-1,K-1)+1;
g.resize(N);
vector<int> s(m),t(m);
for(int i=0;i<m;i++){
cin>>s[i]>>t[i];s[i]--;t[i]--;
s1[s[i]]=i;
t1[t[i]]=i;
}
for(int i=0;i<m;i++){
int l=lca(s[i],t[i]);
add1(i,jump[0][s[i]],deep[s[i]]-deep[l]);
add1(i,t[i],deep[t[i]]-deep[l]);
}
for(int i=0;i<m;i++){
int l=lca(s[i],t[i]);
add2(i,s[i],deep[s[i]]-deep[l]);
add2(i,jump[0][t[i]],deep[t[i]]-deep[l]);
}
for(int j=K-1;j>0;j--){
for(int i=0;i<n;i++){
g[num1(i,j)].push_back(num1(i,j-1));
g[num1(i,j)].push_back(num1(jump[j-1][i],j-1));
}
}
for(int j=K-1;j>0;j--){
for(int i=0;i<n;i++){
g[num2(i,j-1)].push_back(num2(i,j));
g[num2(jump[j-1][i],j-1)].push_back(num2(i,j));
}
}
for(int i=0;i<n;i++){
if(s1[i]!=-1){
g[num1(i,0)].push_back(s1[i]);
}
if(t1[i]!=-1){
g[t1[i]].push_back(num2(i,0));
}
}
vector<int> in(N);
for(int i=0;i<N;i++){
for(int j:g[i]){
in[j]++;
}
}
queue<int> q;
for(int i=0;i<N;i++){
if(in[i]==0){
q.push(i);
}
}
int cnt=0;
while(q.size()){
int p=q.front();
q.pop();
cnt++;
for(int j:g[p]){
in[j]--;
if(in[j]==0){
q.push(j);
}
}
}
if(cnt==N){
cout<<"Yes"<<'\n';
}
else{
cout<<"No"<<'\n';
}
}
signed main(){
ios_base::sync_with_stdio(false);
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... |