15900: 나무 탈출

각 리프 노드로부터 루트 노드로까지의 총합!

각각의 노드에 층수를 매긴 후 , BFS로 층 수 다 더하기

 

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
long long num = 0;
bool check[500001];
int height[500001];

void BFS(vector<int>* v, int index) {
queue<int> q;

int i,temp,next;
check[index] = true;
q.push(index);
while (!q.empty()) {
temp = q.front();

q.pop();
if (temp != 1 && v[temp].size() == 1) // 자식 없음
{
num += height[temp];
continue;
}
for (i = 0; i < v[temp].size(); i++) {
next = v[temp][i];
if (check[next] == false) {
check[next] = true;
height[next] = height[temp] + 1;
q.push(next);
}
}
}

}


int main(void)
{
int N,i,a,b;
cin >> N;
vector<int>* v = new vector<int>[N + 2];
for (i = 1; i < N; i++) {
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
BFS(v, 1);;
if (num % 2 == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;
}