题目
提交记录

#include<bits/stdc++.h>
using namespace std;
const int unreal_dfn=0,unreal_scc=0;
int dfncnt=unreal_dfn,sccnum=unreal_scc;
vector<int>dfn,low,scc;
stack<int>s;
void tarjan(const std::vector<int>e[],int u,int f/*,std::vector<bool> &instack*/)
{
    low[u]=dfn[u]=++dfncnt;
    s.push(u);
    for(auto v:e[u])
    {
        if(v==f)continue;
        if(dfn[v]==unreal_dfn)
        {
            tarjan(e,v,u/*,instack*/);
            low[u]=min(low[u],low[v]);
        }
        else if(scc[v]==unreal_scc)
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        sccnum++;
        while(!s.empty())
        {
            scc[s.top()]=sccnum;
            if(s.top()==u)
            {
                s.pop();
                break;
            }
            else
            {
                s.pop();
            }
        }
    }
}//tarjan
const int maxn=5e5+1;
const int log2maxn=18;
int lca_depth[maxn],lca_fa[maxn][log2maxn+1],a[maxn],ans,cha[maxn],a2[maxn];
vector<int>edge[maxn],lca_edge[maxn];
void lca_dfs(const int u,const int f,const vector<int>e[])
{
    lca_depth[u]=lca_depth[f]+1;
    lca_fa[u][0]=f;
    for(int i=1;(1<<i)<=lca_depth[u];i++)
        lca_fa[u][i]=lca_fa[lca_fa[u][i-1]][i-1];
    for(auto ed:e[u])
    {
        if(ed!=f)
            lca_dfs(ed,u,e);
    }
    return;
}
int lca(int x,int y)
{
	if(lca_depth[x]<lca_depth[y])
        swap(x,y);
	while(lca_depth[x]>lca_depth[y])
		x=lca_fa[x][(int)log2(lca_depth[x]-lca_depth[y])];
	if(x==y) return x;
	for(int i=min(log2(lca_depth[x]),log2(lca_depth[y]));i>=0;i--)
		if(lca_fa[x][i]!=lca_fa[y][i])
		{
			x=lca_fa[x][i];
			y=lca_fa[y][i];
		}
	return lca_fa[x][0];
}
//LCA
//lca
void dfs2(int u,int f)
{
    for(auto v:lca_edge[u])
    {
        if(v!=f)
        {
            dfs2(v,u);
            cha[u]+=cha[v];
        }
    }
}
int main()
{
    int n,m,q;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfn=vector<int>(n+1,unreal_dfn);
    low=vector<int>(n+1,unreal_dfn);
    scc=vector<int>(n+1,unreal_scc);
    for(int i=1;i<=n;i++)
        if(dfn[i]==unreal_dfn)
            tarjan(edge,i/*,instack*/,0);
    for(int i=1;i<=n;i++)
    {
        a2[scc[i]]+=a[i];
        for(auto v:edge[i])
        {
            if(scc[i]!=scc[v])
            {
                lca_edge[scc[i]].push_back(scc[v]);
            }//因为已经连了无向边，所以这里连一次就够
        }
    }
    lca_depth[0]=0;
    lca_dfs(scc[1],0,lca_edge);//根为 scc[1]
    scanf("%d",&q);
    for(int i=1,x,y,lca_xy;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        x=scc[x];
        y=scc[y];
        lca_xy=lca(x,y);
        cha[x]++;
        cha[y]++;
        cha[lca_xy]--;
        if(lca_fa[lca_xy][0]!=0)
            cha[lca_fa[lca_xy][0]]--;//树上差分
    }
    dfs2(scc[1],0);
    for(int i=1;i<=sccnum;i++)
        if(cha[i]>0)
            ans+=a2[i];//重复只算一次
    printf("%d\n",ans);
    return 0;
}