P7737 [NOI2021] 庆典

lndjy · 2021-08-16 14:56:08 · 题解

这里提供一个虚树的做法，比起其他做法细节少了很多，并且可以扩展到 \sum k\le 10^5。

前面的部分和其他做法一样，先 tarjan 转 DAG，然后拓扑排序变成叶向树，变成树上问题。

随着 k 的增长，分类讨论变得麻烦，考虑虚树。

将 s,t 以及所有新边的两个端点拿出来，建立虚树，从祖先到后代连单向边（因为是叶向树）。同时点带点权为树上的点权，边带边权为两点之间不含两个端点的点权和。对于新加的边，根据定义在虚树上面多连一个边权为 0 的边。

现在变成和一开始一样的问题：给定一个的有向图，求 s 到 t 可能经过的权值和，只不过点边较少。

既然点边较少，那么原来的 35 分暴力做法就派上用场了：建原图跑出 s 到达的点边，建反图跑出 t 到达的点边，最后取一个交累加进答案。

代码较长，但是各部分互相独立比较好调，调试时只需要检查各种新图是不是对的就行了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<unordered_map>
#include<map>
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
const int N=3e5+5;
int n,m,q,k,head[N],cnt,d[N];
struct Graph
{
    int head[N],cnt;
    struct edge
    {
        int to,nxt;
    }e[N*2];
    void add(int u,int v)
    {
        e[++cnt].to=v;
        e[cnt].nxt=head[u];
        head[u]=cnt;
    }
}G1,G2;
struct graph
{
    int head[20],cnt;
    struct edge
    {
        int to,nxt,v;
    }e[30*2];
    void add(int u,int v,int w)
    {
//      cout<<u<<" "<<v<<" "<<w<<endl;
        e[++cnt].to=v;
        e[cnt].nxt=head[u];
        head[u]=cnt;
        e[cnt].v=w;
    }
    void clear()
    {
        cnt=0;
        memset(head,0,sizeof head);
    }
}G3,G4;
struct edge
{
    int to,nxt;
}e[N*2];
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int dfn[N],low[N],v[N],col[N],colw[N],tot,s[N],top,Sum,st,ed,h[15],sum[N],lg[N],f[N][20],dep[N],Tot,L[N],ind[N];
#define sum Sum
void dfs(int now)//原图 tarjan 
{
    dfn[now]=low[now]=++tot;
    s[++top]=now;
    v[now]=1;
    for(int i=head[now];i;i=e[i].nxt)
    if(!dfn[e[i].to]) dfs(e[i].to),low[now]=min(low[now],low[e[i].to]);
    else if(v[e[i].to]) low[now]=min(low[now],dfn[e[i].to]);
    if(low[now]==dfn[now])
    {
        int x;
        sum++;
        do
        {
            x=s[top--];
            col[x]=sum;
            v[x]=0;
            colw[sum]++;
        }while(now!=x);
    }
}
void topo()//G1DAG->G2 tree 
{
    queue<int> q;
    for(int i=1;i<=sum;i++)
    if(!d[i]) q.push(i);
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=G1.head[now];i;i=G1.e[i].nxt)
        {
            d[G1.e[i].to]--;
            if(d[G1.e[i].to]==0)
            {
                G2.add(now,G1.e[i].to);
                ind[G1.e[i].to]++;
            //  cout<<now<<" "<<G1.e[i].to<<endl;
                q.push(G1.e[i].to);
            }
        }
    }
}
#undef sum
struct Hash
{
    unordered_map<int,int> mp;
    int cnt;
    void clear()
    {
        mp.clear();
        cnt=0;
    }
    int get(int x)
    {
        if(mp[x]==0) mp[x]=++cnt;
        return mp[x];
    }
}H;
void dfs1(int now,int fa)//G2 tree dfs ：lca，dfn（L），权值前缀和（sum） 
{
    f[now][0]=fa;
    L[now]=++Tot;
    dep[now]=dep[fa]+1;
    for(int i=1;i<=lg[dep[now]];i++)
    f[now][i]=f[f[now][i-1]][i-1];
    sum[now]=sum[fa]+colw[now];
    for(int i=G2.head[now];i;i=G2.e[i].nxt)
    {
        if(G2.e[i].to!=fa)
        dfs1(G2.e[i].to,now);
    }
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]-1];
    if(x==y) return x;
    for(int i=lg[dep[x]];i>=0;i--) 
    if(f[x][i]!=f[y][i])
    x=f[x][i],y=f[y][i];
    return f[x][0];
}
bool cmp(int x,int y)
{
    return L[x]<L[y];
}
int vis[30],vis2[30],vp[30],val[30];
int work()
{
    memset(vis,0,sizeof vis);
    memset(vp,0,sizeof vp);
    queue<int> q;
//  cout<<H.get(st)<<" "<<H.get(ed)<<endl;
    q.push(H.get(st));
    while(!q.empty())//G3 bfs
    {
        int now=q.front();q.pop();
        vp[now]=1;
        for(int i=G3.head[now];i;i=G3.e[i].nxt)
        {
            if(!vis[i])
            {
                vis[i]=1;
                q.push(G3.e[i].to);
            }
        }
    }
    int ans=0;
    memset(vis2,0,sizeof vis2);
    q.push(H.get(ed));
    while(!q.empty())//G4 bfs
    {
        int now=q.front();q.pop();
        if(vp[now]) ans+=val[now],vp[now]=0;
        for(int i=G4.head[now];i;i=G4.e[i].nxt)
        {
            if(!vis2[i])
            {
                vis2[i]=1;
                if(vis[i]) ans+=G4.e[i].v,vis[i]=0; 
                q.push(G4.e[i].to);
            }
        }
    }
    memset(val,0,sizeof val);
    return ans;
}
int main()
{
    n=read();m=read();q=read();k=read();
    for(int i=1;i<=n;i++)
    lg[i]=lg[i/2]+1;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        add(u,v);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i]) dfs(i);
    for(int i=1;i<=n;i++)
    for(int j=head[i];j;j=e[j].nxt)
    if(col[i]!=col[e[j].to])
    G1.add(col[i],col[e[j].to]),d[col[e[j].to]]++;
    topo();
    int root=0;
    for(int i=1;i<=Sum;i++)
    if(ind[i]==0) root=i;
    dfs1(root,0);
    for(int i=1;i<=q;i++)
    {
        G3.clear();G4.clear();H.clear();
        st=read();ed=read();
        st=col[st];ed=col[ed];
        h[1]=st;h[2]=ed;
        top=0;
        for(int j=1;j<=k;j++)
        {
            int u=read(),v=read();
            u=col[u];v=col[v];
            if(u==v) continue;
            G3.add(H.get(u),H.get(v),0);
            G4.add(H.get(v),H.get(u),0);
            h[j*2+1]=u;h[j*2+2]=v;
        }
        sort(h+1,h+(k+1)*2+1,cmp);
        int qwq=unique(h+1,h+(k+1)*2+1)-h-1;
        for(int j=1;j<=qwq;j++)
        val[H.get(h[j])]=colw[h[j]];
        s[++top]=h[1];
        for(int j=2;j<=qwq;j++)
        {
            int lca=LCA(h[j],s[top]);
            val[H.get(lca)]=colw[lca];
            while(1)
            {
                if(dep[lca]>=dep[s[top-1]])
                {
                    if(lca!=s[top])
                    {
                        G3.add(H.get(lca),H.get(s[top]),sum[f[s[top]][0]]-sum[lca]);
                        G4.add(H.get(s[top]),H.get(lca),sum[f[s[top]][0]]-sum[lca]);
                        if(lca!=s[top-1])
                        s[top]=lca;
                        else top--;
                    }
                    break;
                }
                else
                {
                    G3.add(H.get(s[top-1]),H.get(s[top]),sum[f[s[top]][0]]-sum[s[top-1]]);
                    G4.add(H.get(s[top]),H.get(s[top-1]),sum[f[s[top]][0]]-sum[s[top-1]]);
                    top--;
                }
            }
            s[++top]=h[j];
        }
        while(top-1)
        {
    //      cout<<"qwq";
            G3.add(H.get(s[top-1]),H.get(s[top]),sum[f[s[top]][0]]-sum[s[top-1]]);
            G4.add(H.get(s[top]),H.get(s[top-1]),sum[f[s[top]][0]]-sum[s[top-1]]);
            top--;
        }
        printf("%d\n",work());
    }
    return 0;
}
/*
7 6 1 1
1 2
1 3
2 4
3 5
2 6
6 7
6 4 7 1
*/
/*
5
*/