SoundHound Inc. Programming Contest 2018 -Masters Tournament- : E - + Graph

ちょっと手間取ったけどなんとか全完。
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e

問題

N頂点の連結無向グラフがある。
各辺vにはパラメータS[v]が設定されている。

各頂点に正整数を振ったとき、各辺において両端の値の和がS[v]となるようにしたい。
各頂点の点の振り方は何通りあるか。

解法

辺の一端の頂点の値が決まるともう片方も決まるので、１個頂点の値を決めると他も連鎖的に確定する。
また、ある１個の頂点の値を1増やすと、そこから奇数個辺を辿っていける頂点では値が1減り、偶数個辺を辿っていける頂点では1増える。
よって元のグラフが２部グラフかどうかによって処理を変える。

2部グラフではない場合

ある頂点の値を0とし、各頂点においてそこから辺を奇数・偶数回辿った場合に決まる値を求めよう。
奇数回辿った場合a、偶数回たどった場合bとすると、元々最初の頂点が(a+b)/2に設定されていれば、両者の値が一致することになる。

そこで、最初の頂点を(a+b)/2とした場合、全頂点の値が正となるか確認する。

2部グラフの場合

先頭の頂点を0としたときの値を元に、各頂点の値がどうなるか求めよう。
各頂点において、先頭の頂点を1増やすと合わせて1増えるか1減るかは、先頭の頂点からの距離で一意に決まる。
ここから、各頂点における値が正であるためには、先頭の頂点の値がどの範囲であればいいかが求まる。

全頂点における、前述の値の範囲の共通部分を求めればよい。

int N,M;
vector<pair<int,ll>> E[101010];

ll V[2][2][101010];

void dfs(int id,int st,int cur,ll v) {
	if(V[id][st][cur]==1LL<<60) {
		V[id][st][cur]=v;
		FORR(e,E[cur]) dfs(id,st^1,e.first,e.second-v);
	}
	if(V[id][st][cur]!=v) {
		cout<<0<<endl;
		exit(0);
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	FOR(i,2) FOR(j,2) FOR(x,N) V[i][j][x]=1LL<<60;
	dfs(0,0,0,0);
	dfs(1,0,0,1);
	
	if(V[0][1][0]!=1LL<<60) {
		ll ret=abs(V[0][0][0]-V[0][1][0]);
		FOR(x,N) V[0][0][x]=V[0][1][x]=1LL<<60;
		dfs(0,0,0,ret/2);
		FOR(i,N) if(min(V[0][0][i],V[0][1][i])<=0) {
			cout<<0<<endl;
			return;
		}
		cout<<1<<endl;
	}
	else {
		
		ll L=1,R=1LL<<60;
		for(i=1;i<N;i++) {
			int cur=V[0][0][i]==1LL<<60;
			ll dif=V[1][cur][i]-V[0][cur][i];
			
			if(dif==1) L=max(L,1-V[0][cur][i]);
			if(dif==-1) R=min(R,V[0][cur][i]-1);
		}
		cout<<max(0LL,R-L+1)<<endl;
		
	}
	
	
}

まとめ

もっとすんなりいくかと思ったら意外に手間取った。