oj.uz

Submission #706582

# Submission time Handle Problem Language Result Execution time Memory
706582 2023-03-07T05:34:12 Z pcc Jail (JOI22_jail) C++14
0 / 100
 34 ms 9760 KB 
#include <bits/stdc++.h>
using namespace std;

#define fs first
#define sc second
#define pii pair<int,int>
const int mxn = 2e5+10;
int bit[mxn],idx[mxn],sz[mxn],link_top[mxn],fa[mxn],bs[mxn],dep[mxn];
bitset<mxn> del;
vector<int> tree[mxn];
vector<pii> ask[mxn];
pii dfn[mxn];
int n,m;
int cnt = 0;
vector<pii> req;
bool flag = true;
void modify(int p,int s,int v){
    if(p>s)return;
    for(;p<=s;p+= p&-p)bit[p] += v;
    return;
}
int getval(int p){
    int re = 0;
    for(;p>0;p-=p&-p)re += bit[p];
    return re;
}
void find_sz(int now,int par){
    sz[now] = 1;
    bs[now] = 0;
    for(auto nxt:tree[now]){
        if(del[nxt]||nxt == par)continue;
        dep[nxt] = dep[now]+1;
        find_sz(nxt,now);
        if(!bs[now]||sz[bs[now]]<sz[nxt])bs[now] = nxt;
        sz[now] += sz[nxt];
    }
    // cout<<now<<":"<<sz[now]<<endl;
    return;
}
int find_centroid(int now,int par,int tar){
    for(auto nxt:tree[now]){
        if(nxt == par||del[nxt])continue;
        if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
    }
    return now;
}
void dfs2(int now,int par,int top){
    fa[now] = par;
    link_top[now] = top;
    dfn[now].fs = ++cnt;
    if(bs[now])dfs2(bs[now],now,top);
    for(auto nxt:tree[now]){
        if(nxt == par||del[nxt]||bs[now] == nxt)continue;
        dfs2(nxt,now,nxt);
    }
    dfn[now].sc = ++cnt;
    return;
}
int lca(int a,int b){
    if(b == -1){
        while(a != fa[link_top[a]])a = fa[link_top[a]];
        return a;
    }
    int ta = link_top[a],tb = link_top[b];
    while(ta != tb){
        if(dep[ta]<dep[tb]){
            swap(ta,tb);
            swap(a,b);
        }
        a = fa[ta];
        ta = link_top[a];
    }
    if(dep[a]<dep[b])return a;
    else return b;
}
vector<pii> st;

bool dfs(int now,int par,int nowcen,bool tocen,bool useflag){
    vector<pii> v;
    for(auto nxt:tree[now]){
        if(nxt == par||del[nxt])continue;
        tocen = (tocen||dfs(nxt,now,nowcen,false,true));
    }
    for(auto &i:ask[now]){
        if(lca(i.fs,i.sc) != nowcen)v.push_back(i);
        else req.push_back(i);
        if(tocen&&useflag)flag = false;
        if(i.sc == nowcen)tocen = true;
        else{
            if(getval(dfn[i.sc].sc)-getval(dfn[i.sc].fs-1) != 0&&useflag)flag = false;
            modify(dfn[i.sc].fs,cnt,1);
            st.push_back({dfn[i.sc].fs,1});
        }
    }
//	cout<<now<<' '<<par<<' '<<nowcen<<endl;
    ask[now] = v;
    return tocen;
}

int get_high(int now,int par){
    int re = 1e9;
    for(auto &i:ask[now]){
    	// cout<<now<<' '<<i.sc<<endl;
        re = min(dep[i.sc],re);
    }
    for(auto nxt:tree[now]){
        if(del[nxt]||nxt == par)continue;
        re = min(re,get_high(nxt,now));
    }
    return re;
}
void cd(int now){
    req.clear();
    find_sz(now,now);
    int cen = find_centroid(now,now,(sz[now]+1)/2);
    // cout<<now<<','<<cen<<endl;
    dep[cen] = 1;
    find_sz(cen,cen);
    cnt = 0;
    dfs2(cen,cen,cen);
    // cout<<cen<<endl;
    for(auto nxt:tree[cen]){
        // cout<<now<<','<<nxt<<','<<flag<<endl;
        if(del[nxt])continue;
        if(!ask[cen].empty()){
            if(lca(ask[cen][0].sc,nxt) == nxt){
                if(get_high(nxt,cen) < dep[ask[cen][0].sc])flag = false;
            }
        }
        dfs(nxt,cen,cen,false,true);
        while(!st.empty()){
            modify(st.back().fs,cnt,-st.back().sc);
            st.pop_back();
        }
    }
    del[cen] = true;
    for(auto nxt:tree[cen]){
        if(del[nxt])continue;
        find_sz(nxt,nxt);
        dfs2(nxt,nxt,nxt);
    }
    map<int,int> deg;
    map<int,vector<int>> paths;
    set<int> all;
    for(auto &i:req){
        if(i.sc == cen){
            paths[cen].push_back(lca(i.fs,-1));
            deg[lca(i.fs,-1)]++;
            all.insert(cen);
            all.insert(lca(i.fs,-1));
        }
        else{
            deg[lca(i.fs,-1)]++;
            paths[lca(i.sc,-1)].push_back(lca(i.fs,-1));
            all.insert(lca(i.fs,-1));
            all.insert(lca(i.sc,-1));
        }
    }
//    for(auto &i:paths){
//        cout<<i.fs<<":";cout<<deg[i.fs]<<';';
//        for(auto &j:i.sc)cout<<j<<',';cout<<endl;
//    }
   queue<int> q;
    for(auto &i:all){
        if(deg[i] == 0)q.push(i);
    }
    while(!q.empty()){
        auto now = q.front();
        q.pop();
        for(auto nxt:paths[now]){
            if(!deg[nxt])continue;
            deg[nxt]--;
            if(!deg[nxt])q.push(nxt);
        }
    }
//    for(auto &i:deg)cout<<i.fs<<":"<<i.sc<<',';cout<<endl<<endl;
    for(auto &i:deg)if(i.sc)flag = false;
//	cout<<now<<endl;
    del[cen] = true;
    for(auto nxt:tree[cen]){
    	if(del[nxt])continue;
        cd(nxt);
    }
    return;
}

void solve(){
    flag = true;
    cin>>n;
    for(int i = 1;i<n;i++){
        int a,b;
        cin>>a>>b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    cin>>m;
    req = vector<pii>(m);
    for(int i = 0;i<m;i++){
        int a,b;
        cin>>a>>b;
        ask[a].push_back({a,b});
    }
    cd(1);
    if(flag)cout<<"Yes\n";
    else cout<<"No\n";
    for(int i = 1;i<=n;i++){
        tree[i].clear();
        ask[i].clear();
        cnt = 0;
        del[i] = false;
    }
    return;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
}
/*
1
3
1 2
2 3
1
1 3


1
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9748 KB Output is correct
2 Correct 6 ms 9716 KB Output is correct
3 Correct 5 ms 9748 KB Output is correct
4 Incorrect 34 ms 9760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 8 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 8 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 8 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 8 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9620 KB Output is correct
5 Incorrect 20 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9748 KB Output is correct
2 Correct 6 ms 9716 KB Output is correct
3 Correct 5 ms 9748 KB Output is correct
4 Incorrect 34 ms 9760 KB Output isn't correct
5 Halted 0 ms 0 KB -