代码求调
查看原帖
代码求调
552688
clx201022楼主2023/12/22 21:42
#include<bits/stdc++.h>
using namespace std;
const int unreal_dfn=0,unreal_scc=0;
void tarjan(int &dfncnt,int &sccnum
,std::vector<int> &dfn,std::vector<int> &low,std::vector<int> &scc
,std::stack<int> &s,const std::vector<int>e[],int u/*,std::vector<bool> &instack*/)
{
    low[u]=dfn[u]=++dfncnt;
    s.push(u);
    for(auto v:e[u])
    {
        if(dfn[v]==unreal_dfn)
        {
            tarjan(dfncnt,sccnum,dfn,low,scc,s,e,v/*,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+3],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_fa[u][0]=f;
    lca_depth[u]=lca_depth[f]+1;
    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);
    }
}
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])-1];
	if(x==y) return x;
	for(int i=log2maxn+2;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;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1,x,y;i<=m;i++)
    {
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    int dfncnt=unreal_dfn,sccnum=unreal_scc;
    vector<int>dfn(n+1,unreal_dfn),low(n+1,unreal_dfn),scc(n+1,unreal_scc);
    stack<int>s;
    tarjan(dfncnt,sccnum,dfn,low,scc,s,edge,1/*,instack*/);
    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]=1;
    lca_dfs(scc[1],0,lca_edge);//根为 scc[1]
    cin>>q;
    for(int i=1,x,y;i<=q;i++)
    {
        cin>>x>>y;
        x=scc[x];
        y=scc[y];
        int lca_xy=lca(x,y);
        cha[x]++;
        cha[y]++;
        cha[lca_xy]--;
        cha[lca_fa[lca_xy][0]]--;//树上差分
    }
    dfs2(scc[1],0);
    for(int i=1;i<=sccnum;i++)
        if(cha[i])
            ans+=a2[i];//重复只算一次
    cout<<ans<<endl;
    return 0;
}
2023/12/22 21:42
加载中...