AtCoder ARC #063 : E - 木と整数 / Integers on a Tree

これはうまく解くとあっさり。
http://arc063.contest.atcoder.jp/tasks/arc063_c

問題

木を成す無向グラフが与えられる。
一部の頂点には整数が書き込まれている。
残りの頂点に整数を書き込み、隣接する頂点に書かれた整数同士の差が１となるようにせよ。

解法

Editorialはややこしい方法が書いてあるが、もっと簡単に解くことができる。
値が確定した頂点をPriority Queueなどで小さい順に探索し、探索対象に隣接する頂点のうち値が未確定の頂点は探索対象+1の値を書き込んでいけばよい。
この過程で、もし隣接頂点の値が確定済みでかつ差が１でないのならば、条件を満たす整数の書き込みはできない。

int N,K;
vector<int> E[101010];
int D[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	MINUS(D);
	priority_queue<pair<int,int>> P;
	
	cin>>K;
	FOR(i,K) {
		cin>>x>>y;
		D[x-1]=y;
		P.push({-y,x-1});
	}
	while(P.size()) {
		int cur=P.top().second;
		P.pop();
		
		FORR(e,E[cur]) {
			if(D[e]==-1) {
				D[e]=D[cur]+1;
				P.push({-D[e],e});
			}
			else {
				if(abs(D[e]-D[cur])!=1) return _P("No\n");
			}
		}
	}
	_P("Yes\n");
	FOR(i,N) _P("%d\n",D[i]);
	
}

まとめ

この回自分は不参加だったけど、参加しても解けてなさそう…。