30pts（WA on # 4,5,9,10）

为什么把 dfs(1,0) 改成 dfs(dcc[1],0)就ac了。

我理解的是这俩的区别就是换了个根dfs，对答案应该没影响啊。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=2e6+10;

int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

int n,m,q,head[N],tot,he[N],tot2=1,d[N],sum[N],w[N],fa[N][20],dep[N];
int dfn[N],low[N],tim,stk[N],top,dcc[N],nw[N],bri[M*2],cnt;
struct node{
	int from,to,nxt;
}edge[M*2],e[M*2];
void add(int x,int y){
	edge[++tot].to=y;
	edge[tot].nxt=head[x];
	head[x]=tot;
}
void ADD(int x,int y){
	e[++tot2].to=y;
	e[tot2].from=x;
	e[tot2].nxt=he[x];
	he[x]=tot2;
}

void tarjan(int x,int in_edge){
	dfn[x]=low[x]=++tim,stk[++top]=x;
	for(int i=he[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]) bri[i]=bri[i^1]=1;
		}
		else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		int y;cnt++;do{
			y=stk[top--],dcc[y]=cnt,nw[cnt]+=w[y];
		}while(x!=y);
	}
}

void dfs(int x,int father){
	for(int i=head[x];i;i=edge[i].nxt){
		int y=edge[i].to;
		if(y==father) continue;
		fa[y][0]=x,dep[y]=dep[x]+1;
		dfs(y,x);
	}
}

void init(){
	for(int i=1;(1<<i)<=cnt;i++)
		for(int j=1;j<=cnt;j++)
			fa[j][i]=fa[fa[j][i-1]][i-1];
}

int lca(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	int k=log2(dep[y]+1);
	for(int i=k;i>=0;i--)
		if(dep[y]-(1<<i)>=dep[x]) y=fa[y][i];
	if(x==y) return x;
	for(int i=k;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

void DFS(int x,int father){
	sum[x]=d[x];
	for(int i=head[x];i;i=edge[i].nxt){
		int y=edge[i].to;
		if(y==father) continue;
		DFS(y,x);
		sum[x]+=sum[y];
	}
}

int main(){
	
	n=read(),m=read();
	for(int i=1;i<=n;i++) w[i]=read();
	for(int i=1;i<=m;i++){int x=read(),y=read();ADD(x,y),ADD(y,x);}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
	for(int i=2;i<=tot2;i++) if(bri[i]) add(dcc[e[i].from],dcc[e[i].to]);
	dfs(dcc[1],0),init(),q=read();//dfs(1,0)->dfs(dcc[1],0)
	while(q--){
		int x=read(),y=read();x=dcc[x],y=dcc[y];int LCA=lca(x,y);
		d[x]++,d[y]++,d[LCA]--,d[fa[LCA][0]]-=2;
	}
	DFS(dcc[1],0);int ans=0;//DFS(1,0)->DFS(dcc[1],0)
	for(int i=1;i<=cnt;i++) if(sum[i]>=1) ans+=nw[i];
	cout<<ans<<endl;
	
	return 0;
}