省选连结 day3 T4 求调 RE0

[赵泽龙]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct edge
{
    int nxt,to;
}e[maxn << 1];
int head[maxn],tot;
vector<int> g[maxn];
int dep[maxn];
int deg[maxn];
int poss[maxn],post[maxn];
int ids[maxn][25],idt[maxn][25];
int p[maxn][25];
int f[maxn];
int s[maxn],t[maxn];
int cnt;
int n,m;
void add_edge(int u,int v)
{
    if(u && v)
    {
        e[++tot].nxt = head[u];
        head[u] = tot;
        e[tot].to = v;
        deg[v]++;
    }
}
void dfs(int u,int fa)
{
    f[u] = fa;
    dep[u] = dep[fa] + 1;
    p[u][0] = u;
    ids[u][0] = poss[u];
    idt[u][0] = post[u];
    for(int i = 1;i <= 19;i++)
    {
        int cur = f[p[u][i - 1]];
        p[u][i] = p[cur][i - 1];
        if(!p[u][i])break;
        ids[u][i] = ++cnt;
        add_edge(ids[u][i - 1],cnt);
        add_edge(ids[cur][i - 1],cnt);
        idt[u][i] = ++cnt;
        add_edge(cnt,idt[u][i - 1]);
        add_edge(cnt,idt[cur][i - 1]);
    }
    for(int v : g[u])
    {
        if(v == fa)continue;
        dfs(v,u);
    }
}
int lca(int u,int v)
{
    if(dep[u] < dep[v])swap(u,v);
    for(int i = 17;i >= 0;i--)
    {
        if(dep[p[u][i]] > dep[v])
        {
            u = f[p[u][i]];
        }
    }
    if(u == v)return u;
    for(int i = 17;i >= 0;i--)
    {
        if(f[p[u][i]] != f[p[v][i]])
        {
            u = f[p[u][i]];
            v = f[p[v][i]];
        }
    }
    return f[u];
}
void cals(int u,int s,int t,bool lim)
{
    for(int i = 17;i >= 0;i--)
    {
        if(dep[p[s][i]] > dep[t])
        {
            add_edge(ids[s][i],u);
            s = f[p[s][i]];
        }
    }
    if(!lim)add_edge(ids[s][0],u);
}
void calt(int u,int s,int t,bool lim)
{
    for(int i = 17;i >= 0;i--)
    {
        if(dep[p[s][i]] > dep[t])
        {
            add_edge(u,idt[s][i]);
            s = f[p[s][i]];
        }
    }
    if(!lim)add_edge(u,idt[s][0]);
}
void calc(int u,int s,int t)
{
    int mid = lca(s,t);
    if(s == mid)
    {
        cals(u,t,s,1);
    }
    else
    {
        cals(u,f[s],mid,0);
        cals(u,t,mid,1);
    }
    if(t == mid)
    {
        calt(u,s,t,1);
    }
    else
    {
        calt(u,f[t],mid,0);
        calt(u,s,mid,1);
    }
}
void solve()
{
    cin >> n;
    for(int i = 1;i <= n;i++)g[i].clear();
    tot = 0;
    memset(head,0,sizeof(head));
    memset(p,0,sizeof(p));
    memset(f,0,sizeof(f));
    memset(ids,0,sizeof(ids));
    memset(idt,0,sizeof(idt));
    memset(s,0,sizeof(s));
    memset(t,0,sizeof(t));
    for(int i = 1;i < n;i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> m;
    for(int i = 1;i <= m;i++)
    {
        cin >> s[i] >> t[i];
        poss[s[i]] = i;
        post[t[i]] = i;
    }
    memset(deg,0,sizeof(deg));
    cnt = m;
    dfs(1,0);
    for(int i = 1;i <= m;i++)
    {
        calc(i,s[i],t[i]);
    }
    queue<int> q;
    for(int i = 1;i <= cnt;i++)
    {
        if(!deg[i])
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u];i;i = e[i].nxt)
        {
            int v = e[i].to;
            if(!--deg[v])q.push(v);
        }
    }
    for(int i = 1;i <= cnt;i++)
    {
        if(deg[i])return cout << "No\n",void();
    }
    cout << "Yes\n";
}
int main()
{
    int T;
    cin >> T;
    while(T--)solve();
    return 0;
}

[周子寓 (zzy10124)]

%%%
省选大佬