P7924 「EVOI-RD2」旅行家

· · 题解

算法标签才是一切灵感的源泉

思路：

打开标签一看：缩点。

我们分析下面给的图，可以发现，我们把两条从 1 到 6 的路径叠起来，就可以覆盖由红色框框圈住的强连通分量，从而获得该强连通分量内所有的点的权值。

因此我们可以先缩点，把图简化成一棵树。

再打开标签一看：LCA。

接下来，因为一条边只能经过一次，所以会出现下面这种情况：

（注：此图跟上图不匹配。）

发现没？不就是求两个点的 LCA，再把这两个点与 LCA 之间所有的点（包括这两个点和 LCA）的权值加入答案嘛。

但如何维护答案呢？

又打开标签一看：差分。

我们可以用树上差分来记录一个点的经过次数和该点的儿子的经过次数的差。

最后往下一个 dfs，把差分数组合并，如果该点被经过至少一次，则把该点权值加入答案。

代码：

#include<bits/stdc++.h>
#define N 2000010
#define int long long
using namespace std;
struct hhh{
    int v,next;
}dl[2*N];
int n,m,q,x,y,u[N],v[N],tot,cnt,top,sum,logn,ans;
int a[N],head[N],dfn[N],low[N],stk[N],vis[N],col[N],jh[N],used[N],dep[N],f[N][30],yys[N];//yys即差分数组
void qxx(int u,int v){
    dl[++tot].v=v;
    dl[tot].next=head[u];
    head[u]=tot;
}
void tarjan(int x,int fa){//缩点
    dfn[x]=low[x]=++cnt;
    stk[++top]=x;
    vis[x]=1;
    for(int i=head[x];i;i=dl[i].next){
        int v=dl[i].v;
        if(v==fa) continue;
        if(!dfn[v]) tarjan(v,x),low[x]=min(low[x],low[v]);
        else if(vis[v]) low[x]=min(low[x],low[v]);
    }
    if(dfn[x]==low[x]){
        sum++;
        while(stk[top+1]!=x){
            col[stk[top]]=sum;
            jh[sum]+=a[stk[top]];
            vis[stk[top]]=0;
            top--;
        }
    }
}
void build(int u,int h){//建立LCA
    dep[u]=h;
    for(int i=1;i<=logn;i++){
        if(h<=(1<<i)) break;
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=dl[i].next){
        int v=dl[i].v;
        if(vis[v]) continue;
        vis[v]=1;
        f[v][0]=u;
        build(v,h+1);
    }
}
int lca(int x,int y){//求LCA
    if(dep[x]<dep[y]) swap(x,y);
    int cha=dep[x]-dep[y];
    for(int i=0;i<=logn;i++) if(cha&(1<<i)) x=f[x][i];
    if(x==y) return x;
    for(int i=logn;i>=0;i--){
        if(!dep[f[x][i]]||f[x][i]==f[y][i]) continue;
        x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}
void Go(int x){//合并差分数组
    for(int i=head[x];i;i=dl[i].next){
        int v=dl[i].v;
        if(v==f[x][0]) continue;
        Go(v);
        yys[x]+=yys[v]; 
    }
    if(yys[x]) ans+=jh[x];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
        qxx(u[i],v[i]),qxx(v[i],u[i]);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1);
    tot=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=m;i++) if(col[u[i]]!=col[v[i]]) qxx(col[u[i]],col[v[i]]),qxx(col[v[i]],col[u[i]]);
    vis[1]=1;
    logn=log2(sum)+1;
    build(1,1);
    cin>>q;
    while(q--){
        cin>>x>>y;
        int fa=lca(col[x],col[y]);
        yys[col[x]]++,yys[col[y]]++;
        yys[fa]--,yys[f[fa][0]]--;
    }
    Go(1);
    cout<<ans;
    return 0;
}