Codeforces ECR #078 : E. Tests for problem D

こういう形で2問が連続するのは目新しいな。
https://codeforces.com/contest/1278/problem/E

問題

先ほどの問題の逆である。
Codeforces ECR #078: D. Segment Tree - kmjp's blog

木を成す無向グラフが与えられる。
このような木を成す区間群を構築せよ。

解法

オイラーツアー順に両端の座標を振っていけばよい。

int N;
vector<int> E[505050];
queue<int> Q;
int L[505050],R[505050];
void dfs(int cur,int pre) {
	FORR(e,E[cur]) if(e!=pre) {
		L[e]=Q.front();
		Q.pop();
	}
	R[cur]=Q.front();
	Q.pop();
	reverse(ALL(E[cur]));
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N-1) {
		scanf("%d%d",&x,&y);
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,2*N) Q.push(i+1);
	
	L[0]=1;
	Q.pop();
	dfs(0,0);
	
	FOR(i,N) {
		_P("%d %d\n",L[i],R[i]);
	}
	
}

まとめ

Dより簡単だよね…？