[ZOJ3949 The 17th Zhejiang University Programming Contest B] [트리 DP] Edge to the Root 트리에 한 쪽 뿌리 거리의 합을 최대한 작게

Edge to the Root
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
#include
#include
#include
#include
#include
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 2e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
vectora[N];	// 
int sz[N];			//    
int dep[N];			//   root   
LL sumdis;			//      
int b[N];			//       
LL ans;
void getbg(int x, int fa)
{
	sumdis += dep[x];
	sz[x] = 1;
	for (auto y : a[x])if (y != fa)
	{
		dep[y] = dep[x] + 1;
		getbg(y, x);
		sz[x] += sz[y];
	}
}

void dfs(int x, int fa, int p, LL tmp)
{
	b[dep[x]] = x;
	if (dep[x] == 2)
	{
		p = dep[x];
		tmp -= sz[x];
	}
	else if(p)
	{
		int u = b[p];
		int d1 = dep[u];
		int d2 = dep[x] - dep[u] + 1;
		if (d1 <= d2)++p;
	}
	gmin(ans, tmp);

	for (auto y : a[x])if (y != fa)
	{
		if (!p)
		{
			dfs(y, x, p, tmp);
		}
		else
		{
			dfs(y, x, p, tmp - sz[y] + sz[b[p]] - sz[y]);
		}
	}
}
int main()
{
	scanf("%d", &casenum);
	for (casei = 1; casei <= casenum; ++casei)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i)a[i].clear();
		for (int i = 1; i < n; ++i)
		{
			int x, y; scanf("%d%d", &x, &y);
			a[x].push_back(y);
			a[y].push_back(x);
		}
		sumdis = dep[1] = 0; getbg(1, 0);
		ans = sumdis; dfs(1, 0, 0, sumdis);
		printf("%lld
", ans); } return 0; } /* 【 】 , 1 , n(2e5) 。 , —— dis(1,1) + dis(1,2) + ... + dis(1,n) 【 】 。 dep[x] x , x root ,root 0, sz[x] x ( x) , —— root root , 。 dep[x] , x dis -= (dep[x] - 1) root->x , y y , 。 , —— 。 , 。 。 x DIS, x y。 sz[y] , -= 1( dep[y] >= 2) , root , += 1( ) , root 。 。 , 1 , dfs 。 */

좋은 웹페이지 즐겨찾기