Codeforces #726 Div2 : F. Figure Fixing

Div2とはいえ最終問の割にAC数が多い。
https://codeforces.com/contest/1537/problem/F

問題

無向グラフが与えられる。
各点には、現在の値と目標の値が設定されている。
ここで、任意の辺を選び、両端の点の値に同じ任意の整数を加算できるものとする。
目標値に到達可能か求めよ。

解法

連結成分毎に考える。
連結成分の全域木を考えると、葉から値を調整して過不足分を親に回していき、最終的に現在値と目標値を一致できるか判定しよう。
ただし、この連結成分に奇閉路が含まれる場合、現在値を2単位で任意に調整可能な点に注意。

int T,N,M;
int V[202020];
int vis[202020];
vector<int> E[202020];
int odd;
ll S[2];

void dfs(int cur,int col) {
	if(vis[cur]>=0) {
		if(vis[cur]!=col) odd++;
		return;
	}
	S[col]+=V[cur];
	vis[cur]=col;
	FORR(e,E[cur]) dfs(e,col^1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) {
			cin>>V[i];
			vis[i]=-1;
			E[i].clear();
		}
		FOR(i,N) {
			cin>>x;
			V[i]=x-V[i];
		}
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		int ok=1;
		FOR(i,N) if(vis[i]==-1) {
			odd=0;
			S[0]=S[1]=0;
			dfs(i,0);
			
			if(odd) {
				S[0]+=S[1];
				if(S[0]%2) ok=0;
			}
			else {
				if(S[0]!=S[1]) ok=0;
			}
			
		}
		if(ok) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

まとめ

まぁF問題とはいえ2000ptだしね。