[UCPC] A번 전단지 돌리기, 백준 19542

https://www.acmicpc.net/problem/19542

19542번: 전단지 돌리기

UCPC 본선 등록을 하지 못해서 본선이 끝난 뒤 공개된 문제를 풀어봤습니다.

 

트리를 탐색하면서 현재 노드에서 리프노드까지의 거리가 D이상인 자식노드로만 탐색하여 거리를 1씩 늘려 나가며, 왕복거리이기 때문에 거리에 2배를 해주시면 됩니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <memory.h>
#include <string>
using namespace std;
typedef long long ll;
int n, s, d;
int tl[100001];
vector<int> v[100001];
bool visit[100001] = { 0, };
int ans = 0;
int dfs(int node,int p) { 
	int _max = 0;
	for (auto nxt : v[node]) {
		if (nxt != p) {
			_max = max(_max,dfs(nxt, node)+1);
		}
	}
	tl[node] = _max;
	return tl[node];
}
void search(int node, int p) {

	for (auto nxt : v[node]) {
		if (nxt != p) {
			if (tl[nxt] >= d) {
				ans += 1;
				search(nxt, node);
				ans += 1;
			}
		}
	}
	return;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	cin >> n >> s >> d;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(s, 0);
	search(s, 0);
	cout << ans;
	
}

 

UCPC 예선 후기

2020/07/27 - [알고리즘] - 2020 UCPC 예선 후기 및 문제 풀이

2020 UCPC 예선 후기 및 문제 풀이