やらかしまくった回。
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加算した状態を作れる。
A━┓ ┏━E C━━D B━┛ ┗━F
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時間以上かかってるんだろ。