AtCoder ARC #117 : D - Miracle Tree

これも割とすんなり解けてよかった。
https://atcoder.jp/contests/arc117/tasks/arc117_d

問題

木を成すN頂点の無向グラフが与えられる。
各頂点vに正整数E[v]を振りたい。
その際、

• 距離がdの2点u-vにおいては、E[u]とE[v]の差はd以上
• max(E)が最小

を満たす例を答えよ。

解法

カウンタを持ちながらDFS順で頂点を訪問し、辺に沿って遷移するたびにカウンタをインクリメントすることを考える。
初訪問した点vがあれば、その時点でE[v]をそのカウンタ値とすることを考えよう。
このEは、明らかに前者の条件を満たす。
あとは後者の条件だが、これを満たすには、DFS順の訪問で辺を戻るケースをできるだけ後ろに回せばよい。

そこで、まずグラフの直径を求めよう。
直径の片方の端からDFS順で頂点を訪問し、その際直径の反対側の端点をできるだけ訪問を遅らせるようにすればよい。
そうすれば、最後に設定される値は(2N-1-(直径))となる。

int N;
vector<vector<int>> E;
ll vis[202020];
int have[202020];

ll id=1;
pair<int,int> farthest(vector<vector<int>>& E, int cur,int pre,int d,vector<int>& D) {
	D[cur]=d;
	pair<int,int> r={d,cur};
	FORR(e,E[cur]) if(e!=pre) r=max(r, farthest(E,e,cur,d+1,D));
	return r;
}

pair<int,vector<int>> diameter(vector<vector<int>>& E) { // diameter,center
	vector<int> D[2];
	D[0].resize(E.size());
	D[1].resize(E.size());
	auto v1=farthest(E,0,0,0,D[0]);
	auto v2=farthest(E,v1.second,v1.second,0,D[0]);
	farthest(E,v2.second,v2.second,0,D[1]);
	pair<int,vector<int>> R;
	R.first = v2.first;
	//両端を取る場合
	R.second.push_back(v1.second);
	R.second.push_back(v2.second);

	return R;
}

int dfs1(int cur,int pre,int tar) {
	if(cur==tar) have[cur]=1;
	vis[cur]=id;
	FORR(e,E[cur]) if(e!=pre) {
		have[cur]|=dfs1(e,cur,tar);
	}
	return have[cur];
}
void dfs2(int cur,int pre) {
	
	vis[cur]=id;
	FORR(e,E[cur]) if(e!=pre) {
		if(have[e]==0) {
			id++;
			dfs2(e,cur);
		}
	}
	FORR(e,E[cur]) if(e!=pre) {
		if(have[e]) {
			id++;
			dfs2(e,cur);
		}
	}
	id++;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	E.resize(N);
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	auto a=diameter(E);
	
	x=a.second[0];
	y=a.second[1];
	dfs1(x,x,y);
	dfs2(x,x);
	FOR(i,N) cout<<vis[i]<<" ";
	cout<<endl;
}

まとめ

600ptにしてはちょっと実装めんどうだな。