Submission #1233675

#TimeUsernameProblemLanguageResultExecution timeMemory
1233675minhpkJail (JOI22_jail)C++20
0 / 100
30 ms55364 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector <int> z[1000005];
int sta[1000005];
int fin[1000005];
int tour;
int euler[2000005];
int high[1000005];
int logarit[1000005];
int st[400001][21];
pair<int,int> v[1000005];

void dfs(int i,int par){
    tour++;
    sta[i]=tour;
    euler[tour]=i;

    for (auto p:z[i]){
         if (p==par){
             continue;
         }
         high[p]=high[i]+1;
         dfs(p,i);
         tour++;
         euler[tour]=i;
    }
    tour++;
    fin[i]=tour;
    euler[tour]=i;
}

void buildst(){
    for (int i=1;i<=tour;i++){
         st[i][0]=euler[i];
    }

    for (int j=1;j<=20;j++){
         for (int i=1;i+(1<<j)-1<=tour;i++){
              int l=st[i][j-1];
              int r=st[i+(1<<(j-1))][j-1];

              if (high[l]<high[r]){
                 st[i][j]=l;
              }else{
                 st[i][j]=r;
              }
         }
    }
}
int cnt[1000005];
int lca(int x,int y){
    int l = min(sta[x], sta[y]);
    int r = max(sta[x], sta[y]);
    int j = logarit[r - l + 1];
    int idx1 = st[l][j];
    int idx2 = st[r - (1 << j) + 1][j];
    return (high[idx1] < high[idx2] ? idx1 : idx2);
}
bool isanc(int x,int y){
    return sta[x]>=sta[y] && fin[x]<=fin[y];
}

bool onpath(int x,int y,int u){
     int l=lca(x,y);
     return ((isanc(x,u) && isanc(u,l)) || (isanc(y,u) && isanc(u,l)));
}

stack<int> s;
vector <int> z1[1000005];
int  pos[1000005];
bool vis[1000005];
void dfs1(int i){
    vis[i]=true;

    for (auto p:z1[i]){
        if (vis[p]){
            continue;
        }
        dfs1(p);
    }
    s.push(i);
}

void solve(){
    int a;
    cin >> a;
    for (int i=1;i<a;i++){
        int x,y;
        cin >> x >> y;
        z[x].push_back(y);
        z[y].push_back(x);
    }
    tour=0;
    dfs(1,0);
    buildst();

    int c;
    cin >> c;
    for (int i=1;i<=c;i++){
         cin >> v[i].first >> v[i].second;
    }

//    cout << "\n";
    bool check=true;
    for (int i=1;i<=c;i++){
         for (int j=1;j<=c;j++){
            if (i==j){
                continue;
            }
              auto [x,y]=v[i];
              auto [u,v1]=v[j];
              if (onpath(x,y,u) ){
                  z1[u].push_back(x);

//                  cout << j << " " << i << "\n";
              }
              if (onpath(x,y,v1) ){
                  z1[x].push_back(v1);
//                  cout << i << " " << j << "\n";
              }
         }
    }

    for (int i=1;i<=a;i++){
         if (!vis[i]){
             dfs1(i);
         }
    }
    int cur=0;
    while (s.size()){
         cur++;
         int x=s.top();
         s.pop();
         pos[x]=cur;
    }
    for (int i=1;i<=a;i++){
         for (auto p:z1[i]){
             if (pos[i]>pos[p]){
                 check=false;
                 break;
             }
         }
    }

    if (check){
        cout << "Yes" << "\n";
    }else{
        cout << "No" << "\n";
    }
    for (int i=1;i<=max(a,c);i++){
         z[i].clear();
         z1[i].clear();
         vis[i]=false;
         pos[i]=0;
    }
    for (int i=1;i<=a;i++){
        for (int j=0;j<=20;j++){
             st[i][j]=0;
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    logarit[2] = 1;
    for(int i = 3; i <= 1000000; i++){
         logarit[i] = logarit[i/2] + 1;
    }
    while (t--){
         solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...