[C++] Tree / codeforces-219-D

https://codeforces.com/problemset/problem/219/D

Problem - 219D - Codeforces

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

int n;

class Node {
public:
	int pt;
	int dsum;			// 아래쪽에서 뒤집어야 하는 개수의 합
	int ans;			// node마다 답을 계산해서 저장해놓아야 함
	int nchild;
	vector<int> AD;		// 인접한 것
	vector<int> DR;		// Edge의 Direction 저장
	vector<int> RS;		// node마다 아래에서 받은 것
};

Node C[200005];

int dfs1(int nd, int PT) // 아래쪽에서 받아서 올리는 것만 계산.
{
	int i, s, rt;		// rt는 내가 leaf인 경우
	C[nd].pt = PT;
	s = C[nd].AD.size();
	C[nd].nchild = 0;
	rt = 0;
	for (i = 0; i < s; i++) {
		if (C[nd].AD[i] != C[nd].pt) {
			C[nd].nchild++;
			C[nd].RS[i] = dfs1(C[nd].AD[i], nd);
		}
	}
	for (i = 0; i < s; i++)
		if(C[nd].AD[i] != C[nd].pt)
			rt += C[nd].RS[i] + C[nd].DR[i];

	C[nd].dsum = rt;
	return rt;
}

void dfs2(int nd, int pt, int uans, int dr) // 
{
	int i, s;
	s = C[nd].AD.size();
	if (pt == 0) {
		C[nd].ans = C[nd].dsum;
	}
	else {
		if (dr == 0)
			C[nd].ans = uans + 1;
		else
			C[nd].ans = uans - 1;
	}

	for (i = 0; i < s; i++) {
		if (C[nd].AD[i] != C[nd].pt) {
			dfs2(C[nd].AD[i], nd, C[nd].ans, C[nd].DR[i]);
		}
	}
	return;
}

int main()
{
	int i, x, y;
	int ans;
	cin >> n;
	for (i = 1; i < n; i++) {
		// 지금은 x -> y 인 방식인데, 
		// DR에 정방향이면 0, 역방향이면 1 저장
		cin >> x >> y;
		C[x].AD.push_back(y); C[x].DR.push_back(0); C[x].RS.push_back(0); // 빈자리 0 잡아둠
		C[y].AD.push_back(x); C[y].DR.push_back(1); C[y].RS.push_back(0);
	}

	dfs1(1, 0);
	dfs2(1, 0, 0, 0);
	ans = 300000;

	for (i = 1; i < n; i++) ans = min(ans, C[i].ans);
	cout << ans << endl;

	for (i = 1; i <= n; i++) {
		//if (i > 1) cout << " ";
		if (ans == C[i].ans) cout << i<< " ";
	}
	cout << endl;

	return 0;
}