Loading...
$N$개의 정점으로 이루어진 트리가 주어진다. 트리에서 두 정점 사이의 경로에 포함된 간선의 개수를 두 정점 사이의 거리라 한다.
트리에 존재하는 모든 정점 쌍 중 거리가 정확히 $K$인 쌍의 개수를 구하라. 이때 정점의 순서만 다른 쌍 $(u, v)$와 $(v, u)$는 같은 쌍으로 세며, $(u, u)$와 같이 두 정점이 동일한 쌍도 포함하지 않는다.
센트로이드 분할(centroid decomposition) 알고리즘을 활용하여 문제를 해결하라.
첫째 줄에 트리의 정점 수 $N$과 구하고자 하는 거리 $K$가 공백으로 구분되어 주어진다.
둘째 줄부터 $N-1$개의 줄에 걸쳐 간선의 정보가 주어진다. 각 줄에는 간선의 양끝 정점 번호 $u$, $v$가 공백으로 구분되어 주어진다.
트리에서 거리가 정확히 $K$인 서로 다른 두 정점 쌍의 개수를 출력하라.
5 2
1 2
2 3
3 4
4 5
3
5 3
1 2
2 3
3 4
4 5
2