CF901D

这种题稍微联想一下类似的就差不多秒掉了。

对于这种要求一条边的权值和两个点有关的构造，找到一个欧拉回路/环类似物，将一条路径每条边的边权依次设成 $x,-x$，可能会有很好的性质。

令下面的“点权”代表所有相邻边权之和，而不是题目所给的 $c$。

对于这题，考虑像上面那样找出一个环构造会发生什么。由于相邻两条边的边权分别加上成 $x,-x$，若环长度为偶数什么都不会发生。若为奇数，容易发现其中有一个点的权值会增加 $2x$，其他什么都不会发生。

同时容易发现，若选出一条 $u$ 到 $v$ 的路径，依次将边权加上 $x,-x$，则 $u$ 的点权会加上 $x$，$v$ 的点权也会发生一些变化。

于是这个图有奇环时的做法已经很显然了：令 $u$ 为奇环上的一点，以其为根拎出一棵生成树，并用上面的方法，对于所有不为 $u$ 的点 $v$，找到 $v$ 到 $u$ 的路径，可以在树上做一个差分，将 $v$ 的点权调整，最后再用这个奇环调整 $u$ 的点权。

为什么这样是对的？首先，树上差分的部分，每条边至多被 $n$ 个点影响，所以此时边权 $w\in[-n^2,n^2]$。然后在奇数环上的调整，由于此时 $u$ 点权 $c$ 也同样有 $c\in[-n^2,n^2]$，所以奇环上的 $x\in[-\frac{n^2}{2},\frac{n^2}{2}]$，加起来的 $w\in [-2n^2,2n^2]$。由于 $c_i$ 和 $deg_i$ 奇偶性相同所以不用考虑奇偶性的问题。

至于原图为二分图的情况，首先容易发现，由于每条边连接一个左部点和一个右部点，所以左部点的点权和一定等于右部点的，否则无解。

然后想到，既然无法调整 $n-1$ 个点再调整剩下一个，那就想是否能调整 $n-2$ 个点后，再让剩下两个点一起调整。

具体地，考虑在左部点和右部点中分别选出一个，和有奇环地情况一样，先将除了这两个点之外的都调整完，然后发现，由于是二分图，所以这两个点之间的路径一定是奇数长度。若找出一条路径，将边权依次加上 $x,-x$，则这两个点的点权会同时增加 $x$。由于已经保证有解，于是这样调整一定可以调整成功。

证明和奇环的情况同理，一定也不会超过 $[-2n^2,2n^2]$。于是做完了。

code：

int n,m,c[N],deg[N],col[N],fa[N],id[N];
ll f[N],g[N],h[N];
int fl,sx,sy,se;
bool pd[N];
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
void dfs1(int u,int F){
	fa[u]=F;
	go(i,u){
		int v=e[i].to;
		if(col[v]){
			if(col[v]==col[u]){
				fl=1,sx=u,sy=v,se=(i+1)/2;
			}
			continue;
		}
		pd[(i+1)/2]=1;
		col[v]=3-col[u];
		dfs1(v,u);
	}
}
void dfs2(int u,int F){
	fa[u]=F,f[u]=c[u]-deg[u];
	go(i,u){
		int v=e[i].to;
		if(!pd[(i+1)/2]||v==F){
			continue;
		}
		id[v]=(i+1)/2;
		dfs2(v,u);
		g[(i+1)/2]+=f[v];
		f[u]-=f[v],f[v]=c[v];
	}
}
void dfs3(int u,int F,int s){
	fa[u]=F;
	if(col[u]==col[s]&&u!=s){
		h[u]+=c[u]-deg[u];
		f[u]=c[u];
	}
	go(i,u){
		int v=e[i].to;
		if(!pd[(i+1)/2]||v==F){
			continue;
		}
		id[v]=(i+1)/2;
		dfs3(v,u,s);
		g[(i+1)/2]+=h[v];
		h[u]-=h[v],h[v]=0;
	}
}
void Yorushika(){
	read(n,m);
	rep(i,1,n){
		read(c[i]);
	}
	rep(i,1,m){
		int u,v;read(u,v);
		add(u,v),add(v,u);
		deg[u]++,deg[v]++;
	}
	col[1]=1,dfs1(1,0);
	rep(i,1,n){
		f[i]=deg[i];
	}
	rep(i,1,m){
		g[i]=1;
	}
	if(fl){
		dfs2(sx,0);
		ll d=f[sx]/2,u=sy;
		while(u!=sx){
			if(col[u]==col[sx]){
				g[id[u]]-=d;
			}else{
				g[id[u]]+=d;
			}
			u=fa[u];
		}
		g[se]+=d;
	}else{
		ll x=0,y=0;
		rep(i,1,n){
			if(col[i]==1){
				x+=c[i];
			}else{
				y+=c[i];
			}
		}
		if(x!=y){
			puts("NO");
			return;
		}
		int u=1,v=0;
		rep(i,1,n){
			if(col[i]!=col[1]){
				v=i;
				break;
			}
		}
		dfs3(u,0,u);
		h[u]=0,dfs3(v,0,v);
		ll d=c[v]+h[v]-deg[v];
		while(u!=v){
			if(col[u]==col[v]){
				g[id[u]]-=d;
			}else{
				g[id[u]]+=d;
			}
			u=fa[u];
		}
	}
	puts("YES");
	rep(i,1,m){
		printf("%lld\n",g[i]);
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}