https://codeforces.com/problemset/problem/219/D
Problem - 219D - Codeforces
codeforces.com
#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;
}

'Algorithm Study > c++' 카테고리의 다른 글
| [C++] queue 사용 & 예제 (0) | 2023.06.09 |
|---|---|
| [C++] stack 사용 & 예제 (0) | 2023.06.09 |
| [C++] Prefix sum & static_cast / codeforces-276-C (0) | 2023.06.09 |
| [C++] Longest Increasing Subsequence / codeforces-486-E (0) | 2023.06.07 |
| [C++] Prefix sum(구간합) 알고리즘 (0) | 2023.03.15 |