제출 #1135324

#제출 시각아이디문제언어결과실행 시간메모리
1135324ace5Jail (JOI22_jail)C++20
0 / 100
5097 ms62236 KiB
#include <bits/stdc++.h>

using namespace std;

const int maxn = 120005;
const int maxlog = 19;

pair<int,int> segTree[2][maxn];
int fenv[maxn];
int n;

void add(int i,int x)
{
    for(int j = i+1;j <= n;j += ((j)&(-j)))
    {
        fenv[j] += x;
    }
}
int get(int l,int r)
{
    r++;
    int ans = 0;
    for(int j = r;j > 0;j -= ((j)&(-j)))
    {
        ans += fenv[j];
    }
    for(int j = l;j > 0;j -= ((j)&(-j)))
    {
        ans -= fenv[j];
    }
    return ans;
}

void modify(int i,int x,int l,int r,int indV,int j)
{
    if(l > i || r < i)
        return ;
    else if(l == r)
    {
        segTree[j][indV] = {x,l};
        return ;
    }
    int m = (l+r)/2;
    modify(i,x,l,m,indV*2+1,j);
    modify(i,x,m+1,r,indV*2+2,j);
    segTree[j][indV] = max(segTree[j][indV*2+1],segTree[j][indV*2+2]);
    return ;
}
pair<int,int> get(int lx,int rx,int l,int r,int indV,int j)
{
    if(l > rx || r < lx)
        return {-1,-1};
    else if(l >= lx && r <= rx)
    {
        return segTree[j][indV];
    }
    int m = (l+r)/2;
    pair<int,int> sl = get(lx,rx,l,m,indV*2+1,j);
    pair<int,int> sr = get(lx,rx,m+1,r,indV*2+2,j);
    return max(sl,sr);
}

int st[maxn],en[maxn];
int head[maxn],sz[maxn];
vector<int> g[maxn];
int par[maxn];
int tin[maxn],tout[maxn];
int itin[maxn];
vector<pair<int,int>> paths;
int times = 0;
int vis[maxn];
int binup[maxlog][maxn];
map<int,set<int>> plca;

void dfs1(int v,int p)
{
    sz[v] = 1;
    par[v] = p;
    for(int i = 0;i < g[v].size();++i)
    {
        if(g[v][i] != p)
        {
            dfs1(g[v][i],v);
            sz[v] += sz[g[v][i]];
            if(g[v][0] == p || sz[g[v][i]] > sz[g[v][0]])
                swap(g[v][i],g[v][0]);
        }
    }
    return ;
}

void dfs2(int v,int p,int th)
{
    head[v] = th;
    tin[v] = times++;
    itin[tin[v]] = v;
    for(int i = 0;i < g[v].size();++i)
    {
        if(g[v][i] != p)
        {
            dfs2(g[v][i],v,(i == 0 ? th : g[v][i]));
        }
    }
    tout[v] = times;
    return ;
}


bool isP(int u,int v)
{
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u,int v)
{
    for(int j = maxlog-1;j >= 0;--j)
    {
        if(!isP(binup[j][u],v))
            u = binup[j][u];
    }
    return (isP(u,v) ? u : par[u]);
}

int get_sum(int u,int v)
{
    int ans =0;
    while(!isP(head[u],v))
    {
        ans += get(tin[head[u]],tin[u]);
        u = par[head[u]];
    }
    while(!isP(head[v],u))
    {
        ans += get(tin[head[v]],tin[v]);
        v = par[head[v]];
    }
    ans += get(min(tin[u],tin[v]),max(tin[u],tin[v]));
    return ans;
}

int getv(int u,int v)
{
    while(!isP(head[u],v))
    {
        pair<int,int> xx = get(tin[head[u]],tin[u],0,n-1,0,0);
        if(xx.first > 0)
        {
            return st[itin[xx.second]];
        }
        u = par[head[u]];
    }
    while(!isP(head[v],u))
    {
        pair<int,int> xx = get(tin[head[v]],tin[v],0,n-1,0,0);
        if(xx.first > 0)
        {
            return st[itin[xx.second]];
        }
        v = par[head[v]];
    }
    pair<int,int> xx = get(min(tin[u],tin[v]),max(tin[u],tin[v]),0,n-1,0,0);
    if(xx.first > 0)
    {
        return st[itin[xx.second]];
    }
    else
        return -1;
}
int geten(int u,int v)
{
    if(!isP(v,u))
    {
        if(plca[v].size())
        {
            return *plca[v].begin();
        }
        else
            return -1;
    }
    else
    {
        for(int j = maxlog-1;j >= 0;--j)
        {
            if(!isP(binup[j][u],v))
                u = binup[j][u];
        }
        int pr = tin[u]-1;
        int sf = tout[u];
        pair<int,int> xx = get(0,pr,0,n-1,0,0);
        if(xx.first > 0)
        {
            return st[itin[xx.second]];
        }
        pair<int,int> xx2 = get(0,pr,0,n-1,0,1);
        if(xx2.first > 0)
        {
            return en[itin[xx2.second]];
        }
        pair<int,int> xx3 = get(sf,n-1,0,n-1,0,0);
        if(xx3.first > 0)
        {
            return st[itin[xx3.second]];
        }
        pair<int,int> xx4 = get(sf,n-1,0,n-1,0,1);
        if(xx4.first > 0)
        {
            return en[itin[xx4.second]];
        }
    }
    return -1;
}

vector<int> ans;

void dfs3(int v)
{
    //cout << v << endl;
    int tlca = lca(paths[v].first,paths[v].second);
   // cout << v << endl;
    plca[tlca].erase(v);
   // cout << v << endl;
    vis[v] = 1;
    modify(tin[paths[v].first],0,0,n-1,0,0);
    modify(tin[paths[v].second],0,0,n-1,0,1);
    while(true)
    {
        int k = getv(paths[v].first,paths[v].second);
        if(k != -1)
        {
            dfs3(k);
        }
        else
        {
            break;
        }
    }
    while(true)
    {
        int k = geten(paths[v].first,paths[v].second);
        if(k != -1)
        {
            dfs3(k);
        }
        else
        {
            break;
        }
    }
    ans.push_back(v);
    return ;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int q;
    cin >> q;
    while(q--)
    {
        cin >> n;
        plca.clear();
        paths.clear();
        ans.clear();
        times = 0;
        for(int i = 0;i < n;++i)
        {
            g[i].clear();
            st[i] = -1;
            en[i] = -1;
        }
        for(int i = 0;i < n-1;++i)
        {
            int u,v;
            cin >> u >> v;
            u--;
            v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
      //  cout << "!" << endl;
        dfs1(0,0);
        dfs2(0,-1,0);
        for(int j = 0;j < maxlog;++j)
        {
            for(int i = 0;i < n;++i)
            {
                binup[j][i] = (j == 0 ? par[i] : binup[j-1][binup[j-1][i]]);
            }
        }
        int m;
        cin >> m;
        for(int i = 0;i < m;++i)
        {
            int u,v;
            cin >> u >> v;
            u--;
            v--;
            plca[lca(u,v)].insert(i);
            st[u] = i;
            en[v] = i;
            paths.push_back({u,v});
            vis[i] = 0;
            modify(tin[u],1,0,n-1,0,0);
            modify(tin[v],1,0,n-1,0,1);
        }
        for(int i = 0;i < m;++i)
        {
            if(!vis[i])
            {
                dfs3(i);
            }
        }
       // for(int i = 0;i < m;++i)
       // {
       //     cout << ans[i] << endl;
       // }
        bool y = 1;
        for(int i = 0;i <= n;++i)
        {
            fenv[i] = 0;
        }
        for(int j = 0;j < m;++j)
        {
            add(tin[paths[j].first],1);
        }
        for(int j = 0;j < m;++j)
        {
            int tt = get_sum(paths[ans[j]].first,paths[ans[j]].second);
            y &= (tt == 1);
            add(tin[paths[ans[j]].first],-1);
            add(tin[paths[ans[j]].second],1);
        }
        cout << (y ? "Yes\n" : "No\n");
    }
}
#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...