Codeforces #572 Div1 A2. Add on a Tree : Revolution

やらかしまくった回。
http://codeforces.com/contest/1188/problem/A2

問題

木を成す無向グラフが与えられる。
各辺には整数が設定されている。各整数は異なっており、かつ偶数である。

初期状態で各辺は値0を持つとする。
葉を選択すると、両者の葉の間の辺に、一律で選択した任意の値を加算することができる。
全辺の整数値を入力に合わせることができるか。
できるならばその手順を示せ。

解法

次数2の辺があると、題意を満たせない。
というのも、この2辺は必ず同じ整数しか取れないためである。

そうでない場合、各辺を1つずつ値を合わせていこう。
各点は次数が1か3以上なので、辺の両端の辺が3以上のケースを考える。
以下のケースを考えよう。A-C、B-C、D-E、D-Fは実際は長さが2以上でもよい。
ここでC-D間の値をvにすることを考える。
A-EとB-F間にv/2を加算し、A-BとE-F間で-v/2を減算すると、C-Dだけにv加算した状態を作れる。

Ａ━┓　　┏━Ｅ
　　Ｃ━━Ｄ
Ｂ━┛　　┗━Ｆ

int N;
vector<pair<int,int>> E[101010];
int X[1010],Y[1010];
ll V[1010];
vector<vector<ll>> R;

void go(int x,int y,ll v) {
	if(v==0) return;
	if(x==y) return;
	R.push_back({x,y,v});
}

int getl(int cur,int pre) {
	if(E[cur].size()==1) return cur;
	FORR(e,E[cur]) if(e.first!=pre) return getl(e.first,cur);
}

vector<int> leaf(int cur,int pre) {
	vector<int> L;
	
	if(E[cur].size()==1) {
		return {cur,cur};
	}
	else {
		FORR(e,E[cur]) if(e.first!=pre) L.push_back(getl(e.first,cur));
	}
	return L;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>X[i]>>Y[i]>>V[i];
		X[i]--;
		Y[i]--;
		E[X[i]].push_back({Y[i],i});
		E[Y[i]].push_back({X[i],i});
	}
	FOR(i,N) if(E[i].size()==2) return _P("NO\n");
	
	FOR(i,N-1) if(V[i]) {
		vector<int> L[2];
		L[0]=leaf(X[i],Y[i]);
		L[1]=leaf(Y[i],X[i]);
		ll v=V[i];
		go(L[0][0],L[1][0],v/2);
		go(L[0][1],L[1][1],v/2);
		go(L[0][0],L[0][1],-v/2);
		go(L[1][0],L[1][1],-v/2);
	}
	
	cout<<"YES"<<endl;
	cout<<R.size()<<endl;
	FORR(v,R) cout<<v[0]+1<<" "<<v[1]+1<<" "<<v[2]<<endl;
	
	
	
}

まとめ

あれ、なんで本番これに1時間以上かかってるんだろ。