题解 P7924 「EVOI-RD2」旅行家

· · 题解

Update ：核心证明已给出。

题面翻译：

给出一张无向图，每一个点有点权。现给出 q 组 (x,y)，求所有 x 到所有对应 y 的路径上的边双连通分量的点权和。

有点懵，对吧？为什么是边双连通分量呢？来看：

分析

缩点

如图（黑色为点编号，红色为点权）： 当有这么一对 (1,6) 时，小 A 会把从 1 到 5 的路径都走遍，再走到 6。

如果往后走不会走到死胡同里，就接着走。

Q: 那这个“死胡同”是什么？

A: 一个新的边双连通分量 。（毕竟算法标签里有缩点嘛）

Q: 为什么？

A:

我们知道，两个边双是由一条割边连接起来的，而且在一个连通图中，任意两个边双的路径唯一。

即：从甲边双到乙边双间有一条边与之相连，而这条边便是从甲到乙的“必经之路”

而题目中说：点可以重复经过，而边不可以。

即在同一条路径中，一条边不能经过两次。

而在同一个边双里面，由于没有割边的限制，于是可以保证里面的点便都可以到达，而不会出现走回头路的情况。

因为同一个边双里的点之间的路径上没有割边，且路径不唯一。

但是如果过了终点所在的边双，就不能够通过割边返回了。

于是一个旅游季的答案为：从 x 到 y 所经过边双里的点的点权之和。

还不明白什么是边双，以及如何缩点的OIer请自行查找博客。

PS：

这些点可以缩到一起：

LCA

缩完点，这个图立马清晰得多了：

对于一个无向图，由于它是连通的，所以剩下来的是一个无根树。

而求两个点所在的边双的路径的话，就有请 LCA 登场！

LCA 之前要先跑一遍 DFS 转换为有根树。

LCA 用的便是喜闻乐见的倍增大法。代码里有完整模板。

树上差分

由于要统计点权之和，而且 重复经过的只统计一次！

所以传统的树上差分改一下，改成标记差分：过一个点，标记++。

标记 \geq 1 的，加入到答案内即可。

一定要注意：是点权而不是边权。

模板也在代码内。

#include<bits/stdc++.h>
using namespace std;
const int N=800005;
int n,m,a[N],tot,head[N],q,dfn[N],low[N],inx,st[N],top,bel[N],cnt,val[N],dis[N];
long long cha[N];
bool in[N];
struct EDGE{
    int v,nxt;
}ed[N<<3];
void add(int u,int v){
    ed[++tot]={v,head[u]};
    head[u]=tot;
}
void tarjan(int x,int f){
    low[x]=dfn[x]=++inx;
    st[++top]=x;in[x]=true;
    for(int i=head[x];i;i=ed[i].nxt){
        int v=ed[i].v;
        if(v==f) continue;
        if(!dfn[v]){
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
        }
        else if(in[v]) low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x]){
        int y;++cnt;
        while(y=st[top--]){
            val[cnt]+=a[y];
            in[y]=false;
            bel[y]=cnt;
            if(x==y) break;
        }
    }
}
int u[N<<2],v[N<<2],dep[N],fa[N][25];
void dfs(int x,int dept,int f){
    dep[x]=dept;fa[x][0]=f;
    dis[x]=val[x]+dis[f];
    for(int i=head[x];i;i=ed[i].nxt){
        int v=ed[i].v;
        if(v==f) continue;
        dfs(v,dept+1,x);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y])
        x=fa[x][(int)log2(dep[x]-dep[y])-1];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    return fa[x][0];
}
int dfs2(int x,int f){
    for(int i=head[x];i;i=ed[i].nxt){
        int v=ed[i].v;
        if(v==f) continue;
        dfs2(v,x);
        cha[x]+=cha[v];
    }
    return cha[x];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        add(u[i],v[i]);
        add(v[i],u[i]);
    }
    tarjan(1,0);//缩点，因为图是连通的，所以任选一点作为起点
    tot=0;
    memset(head,0,sizeof head);
    for(int i=1;i<=m;i++){
        u[i]=bel[u[i]],v[i]=bel[v[i]];
        if(u[i]!=v[i]) add(u[i],v[i]),add(v[i],u[i]);
    }
    dfs(bel[1],1,0);
    cin>>q;
    for(int i=1;i<=20;i++)
        for(int j=1;j<=cnt;j++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
    int x,y;
    int ans=0;
    for(int i=1;i<=q;i++){ // LCA、树上差分
        scanf("%d%d",&x,&y);
        x=bel[x],y=bel[y];
        int s=lca(x,y);
        cha[x]++;
        cha[y]++;
        cha[s]--;
        cha[fa[s][0]]--;
    }
    dfs2(bel[1],0);//还原标记
    for(int i=1;i<=cnt;i++)
        if(cha[i])
            ans+=val[i];
    cout<<ans;
    return 0;
}