树形DP例3

题面描述

给定一个n个点的无权树，求树的重心.重心定义为，删去该点之后，树中的所有连通块的最大尺寸最小。

输入格式

第一行一个n。

接下来n-1行，每行分别有两个数a和b，表示节点a到节点b有一条无向边。

输出格式

求这棵树的重心（保证唯一）

样例

数据范围

这个题，比前两题难，这个其实就是求一下树的重心，是一个应用，什么是树的重心，题目说明的很清楚，所以在此不再解读题目，主要思想还是dfs，在回溯时记录。先设一个si[]，用来记录边的多少，再用以个de[]来维护每个点的最大连通块的大小，在最后找一个连通块最小的，记录一下下标，输出。

这里面还有一个我当时没有理解的点，就是在回溯时不仅要找一下si[]的最大值，还有在跟n-si[]比一下，因为这个节点是要删除的，他的父亲节点还是要和他的子节点来判断一下，更新一下即可。

代码

#include<bits/stdc++.h>
using namespace std;
int  si[1001000],de[1001000],head[1001000],ver[1001000],ne[1001000],tot=0,b[1001000],n;
void add(int x,int y)
{
	ver[++tot]=y;
	ne[tot]=head[x];
	head[x]=tot;
 } 
void dfs(int x)
{
	b[x]=1;
	for(int i=head[x];i;i=ne[i])
	{
		if(b[ver[i]])
		continue;
		dfs(ver[i]);
		si[x]+=si[ver[i]];
		de[x]=max(si[ver[i]],de[x]);
	}
	de[x]=max(de[x],n-si[x]);//仔细理解含义
}
int main()
{
	freopen("T3.in","r",stdin);
	freopen("T3.out","w",stdout);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)
	si[i]=1;
	dfs(1);
	int op,minn=1000000000;
	for(int i=1;i<=n;i++)
	{
		if(de[i]<minn)
		{
			minn=de[i];
			op=i;
		}
	}
	cout<<op;
	return 0;
}

de[x]=max(de[x],n-si[x]);//仔细理解含义