Submission #706589

#	Time	Username	Problem	Language	Result	Execution time	Memory
706589		pcc	Jail (JOI22_jail)	C++14	0 / 100	67 ms	9804 KiB

jail

#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 mv[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){
	mv[now] = 0;
    vector<pii> v;
    for(auto nxt:tree[now]){
        if(nxt == par||del[nxt])continue;
        tocen = (tocen||dfs(nxt,now,nowcen,false,true));
        mv[now] += mv[nxt];
    }
    for(auto &i:ask[now]){
        if(lca(i.fs,i.sc) != nowcen)v.push_back(i);
        else req.push_back(i);
        mv[now]++;
        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;
        dfs(nxt,cen,cen,false,true);
        if(!ask[cen].empty()){
            if(lca(ask[cen][0].sc,nxt) == nxt){
                if(get_high(nxt,cen) < dep[ask[cen][0].sc])flag = false;
            }
        }
        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:ask[cen]){
    	paths[lca(i.sc,-1)].push_back(cen);
    	deg[cen]++;
	}
   	queue<int> q;
   	all.insert(cen);
   if(!deg[cen])deg[cen] = 0;
   for(auto nxt:tree[cen]){
   		if(!deg[nxt])deg[nxt] = 0;
   		all.insert(nxt);
   		if(del[nxt]||!mv[nxt])continue;
//   		cout<<cen<<' '<<nxt<<":"<<mv[nxt]<<endl;
   		paths[cen].push_back(nxt);
   		deg[nxt]++;
   }
    for(auto &i:all){
//        cout<<i<<":";cout<<deg[i]<<';';
//        for(auto &j:paths[i])cout<<j<<',';cout<<endl;
        if(!deg[i])q.push(i);
    }
    while(!q.empty()){
        auto now = q.front();
        q.pop();
        for(auto nxt:paths[now]){
            if(!deg[nxt])continue;
//            cout<<now<<':'<<nxt<<endl;
            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<<flag<<endl<<endl;
//	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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23