Algorithm/BOJ
UCPC 2020 A / 전단지 돌리기 - 19542
jhg0406
2020. 8. 5. 22:42
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
#include <vector>
using namespace std;
int N, S, D;
int ans = 0;
vector<vector<int>> adj;
vector<int> dept;
vector<int> Mdept;
int dfs(int here) {
int ret = dept[here];
for(int i = 0; i<adj[here].size(); ++i) {
int there = adj[here][i];
if(!dept[there]) {
dept[there] = dept[here] + 1;
ret = max(ret, dfs(there));
}
}
Mdept[here] = ret;
if(Mdept[here] - dept[here] >= D)
ans += 2;
return ret;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> S >> D;
adj = vector<vector<int>>(N+1);
Mdept = dept = vector<int>(N+1, 0);
int u, v;
for(int i = 0; i<N-1; ++i) {
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dept[S] = 1;
dfs(S);
cout << (ans - 2 >= 0 ? ans-2 : 0);
}
|
cs |
https://www.acmicpc.net/problem/19542
19542번: 전단지 돌리기
현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민
www.acmicpc.net
전단지 돌리기
모든 노드에 대해서 (현재노드에서 갈수 있는 가장 깊은 곳의 깊이 - 현재노드의 깊이) >= D 인 노드까지만 가도 모든 곳에 전단지를 배포할 수 있습니다. DFS를 한번만 실행해 정답을 구할 수 있습니다.
