Codeforces #637 Div1 D. Nastya and Time Machine

なんかこの回問題文が長くてつらいな。
https://codeforces.com/contest/1340/problem/D

問題

木を成す無向グラフが与えられる。
頂点1・時刻0から初めて、以下を満たすように移動することを考える。

• 隣接点に移動する。その際時刻は1加算される。
• 今の位置にいたまま、時刻を今の値未満の非負整数に巻き戻す。

各手順における(点番号,時刻)の対を並べたとき、同じ対が2回以上現れないようにしたい。
この時、全頂点を1回以上訪問しつつ、現れる時刻の最大値が最大となる移動経路を求めよ。

解法

親からある頂点に到達したとき時刻がTだったとする。
この時、親にも同じ時刻Tとなるように戻そう。
子頂点数がT以下の時、子頂点をそれぞれ探索して、戻り際に1,2,....T-1となるように戻ってくれば、親に戻るときの時刻もTにできる。
Tより多いとき、先に戻り際がT+1,T+2....となるように子頂点をたどり、その後1,2,....T-1となるようにすればよい。

int N;
vector<int> E[101010];
int vis[101010];
vector<pair<int,int>> T;

void dfs(int cur,int pre,int target) {
	T.push_back({cur,target});
	int num=E[cur].size()-1;
	int x=target;
	target--;
	
	
	FORR(e,E[cur]) if(e!=pre && num>target) {
		vis[e]=1;
		num--;
		dfs(e,cur,++x);
		T.push_back({cur,x});
	}
	
	T.push_back({cur,target-num});
	x=target-num;
	
	FORR(e,E[cur]) if(e!=pre && vis[e]==0) {
		dfs(e,cur,++x);
		T.push_back({cur,x});
	}
	
	assert(target==x);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	T.push_back({1,0});
	FORR(e,E[1]) {
		dfs(e,1,T.back().second+1);
		T.push_back({1,T.back().second+1});
	}
	
	_P("%d\n",(int)T.size());
	FORR(e,T) _P("%d %d\n",e.first,e.second);
}

まとめ

こちらは普通に解けて良かったね。