1w2t 良好码风求条
查看原帖
1w2t 良好码风求条
1625208
wyx1222楼主2025/7/20 14:41
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=x*10+ch-'0'; ch=getchar();
	}
	return x*f;
}
void write(int x){
	if(x<0){
		putchar('-'); x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return ;
}
const int N=5e5+10,M=2e6+10;
int n,m,q,head[N],k,a[N],u[N],v[N];
struct edge{
	int to,next;
}e[M<<1];
void add(int u,int v){
	e[++k]=(edge){v,head[u]};
	head[u]=k;
	e[++k]=(edge){u,head[v]};
	head[v]=k;
}
int dfn[N],low[N],t,cnt,pos[N],w[N]; bool ins[N];
stack <int> s;
void tarjan(int u,int f){
	dfn[u]=low[u]=++t;
	s.push(u);
	ins[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==f) continue;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		cnt++;
		while(1){
			int x=s.top(); s.pop();
			pos[x]=cnt;
			w[cnt]+=a[x];
			ins[x]=0;
			if(x==u) break;
		}
	}
}
int new_head[N],new_k;
edge new_e[M<<1];
void new_add(int u,int v){
	new_e[++new_k]=(edge){v,new_head[u]};
	new_head[u]=new_k;
	new_e[++new_k]=(edge){u,new_head[v]};
	new_head[v]=new_k;
}
int dep[N],fa[N][30];
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	for(int i=1;i<=20;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(int i=new_head[u];i;i=new_e[i].next){
		int v=new_e[i].to;
		if(v!=f) dfs(v,u);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--){
		if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	}
	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 cf[N],ans;
void getans(int u){
	for(int i=new_head[u];i;i=new_e[i].next){
		int v=new_e[i].to;
		if(v==fa[u][0]) continue;
		getans(v);
		cf[u]+=cf[v];
	}
	if(cf[u]) ans+=w[u];
}
int main(){
	n=read(); m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++){
		u[i]=read(); v[i]=read();
		add(u[i],v[i]);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	for(int i=1;i<=m;i++){
		int x=pos[u[i]], y=pos[v[i]];
		if(x!=y) new_add(x,y);
	}
	dfs(pos[1],0);
	q=read();
	while(q--){
		int x=read(),y=read();
		x=pos[x]; y=pos[y];
		int l=lca(x,y);
		cf[x]++; cf[y]++;
		cf[l]--; cf[fa[l][0]]--;
	}
	getans(pos[1]);
	write(ans);
	return 0;
}
2025/7/20 14:41
加载中...