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$ 到达的点边，最后取一个交累加进答案。
代码较长，但是各部分互相独立比较好调，调试时只需要检查各种新图是不是对的就行了。
```cpp
#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
*/
```