[ZOJ3949 The 17th Zhejiang University Programming Contest B] [트리 DP] Edge to the Root 트리에 한 쪽 뿌리 거리의 합을 최대한 작게
4816 단어 문제집. - ZOJ.동적 계획 - 트리 DP
Time Limit: 1 Second
Memory Limit: 131072 KB
Given a tree with n vertices, we want to add an edge between vertex 1 and vertex x, so that the sum of d(1, v) for all vertices v in the tree is minimized, where d(u, v) is the minimum number of edges needed to pass from vertex u to vertex v. Do you know which vertex x we should choose?
Recall that a tree is an undirected connected graph with n vertices and n - 1 edges.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 2 × 105), indicating the number of vertices in the tree.
Each of the following n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n), indicating that there is an edge between vertex u and v in the tree.
It is guaranteed that the given graph is a tree, and the sum of n over all test cases does not exceed 5 × 105. As the stack space of the online judge system is not very large, the maximum depth of the input tree is limited to about 3 × 104.
We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.
Output
For each test case, output a single integer indicating the minimum sum of d(1, v) for all vertices v in the tree (NOT the vertex x you choose).
Sample Input
2
6
1 2
2 3
3 4
3 5
3 6
3
1 2
2 3
Sample Output
8
2
Hint
For the first test case, if we choose x = 3, we will have
d(1, 1) + d(1, 2) + d(1, 3) + d(1, 4) + d(1, 5) + d(1, 6) = 0 + 1 + 1 + 2 + 2 + 2 = 8
It's easy to prove that this is the smallest sum we can achieve.
Author:
WENG, Caizhi
Source: The 17th Zhejiang University Programming Contest Sponsored by TuSimple
#include
#include
#include
#include
#include
#include
#include
#include
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Hdu1520-Anniversary party(트리 dp)(시작 문제)전송문: Anniversary party 제목: 회사 내의 직원 관계표는 하나의 나무로 모든 직원은 하나의 권한을 가진다. 연회를 열 때 한 직원과 그의 직속 상사는 동시에 나타날 수 없다(즉 직접 인접한 노드는 동...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.