树上差分求调!
查看原帖
树上差分求调!
763878
Jerry_heng楼主2024/8/8 17:33
#include<bits/stdc++.h>
#define db double
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f; 
}
const int mxn=5e5+10;
int sum[mxn],dfn[mxn],low[mxn],n,m,s[mxn],be[mxn],tot,dep[mxn],col,f[mxn][31],ans,U[mxn],V[mxn],a[mxn],lg;
stack<int>st;
vector<int>E[mxn],e[mxn];
map<pii,bool>mp;
void tarjan(int u,int f){
	dfn[u]=low[u]=++tot;
	st.push(u);
	for(auto v:E[u]){
		if(v==f)continue;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],low[v]);
	}
	if(low[u]==dfn[u]){
		col++;
		while(st.top()!=u){
			int p=st.top();st.pop();
			sum[col]+=a[p];
			be[p]=col;
		}
		int p=st.top();st.pop();
		sum[col]+=a[p];
		be[p]=col;
	}
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=lg;i>=0;i--)
		if(dep[f[u][i]]>dep[v])u=f[u][i];
	if(u==v)return u;
	for(int i=lg;i>=0;i--)
		if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
	return f[u][0];
}
void dfs1(int u,int fa){
	f[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int i=1;i<=lg;i++)
		f[u][i]=f[f[u][i-1]][i-1];
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs1(v,u);
	}
}
void dfs2(int u,int fa){
	for(auto v:e[u]){
		if(v==f[u][0])continue;
		dfs2(v,u);
		s[u]+=s[v];
	}
	if(s[u]>0)ans+=sum[u];
}
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    	a[i]=read();
    for(int i=1;i<=m;i++){
    	int u=read(),v=read();
    	E[u].pb(v),E[v].pb(u);
    	U[i]=u,V[i]=v;
    }
    for(int i=1;i<=n;i++)
    	if(!dfn[i])tarjan(i,-1);
    for(int i=1;i<=m;i++){
    	if(be[U[i]]!=be[V[i]])e[be[U[i]]].pb(be[V[i]]),e[be[V[i]]].pb(be[U[i]]);
    }
    dfs1(1,0);
    int T=read();
    lg=log2(col)+1;
    while(T--){
    	int u=read(),v=read();
    	u=be[u],v=be[v];
    	int fa=LCA(u,v);
    	s[u]++,s[v]++,s[fa]--,s[f[fa][0]]--;
    }
    dfs2(1,0);
    printf("%d\n",ans);
    return 0;
}
2024/8/8 17:33
加载中...