什么网站做视频最赚钱/路由优化大师

POJ - 1655

接触到了一个新的名词：树的重心，百度百科给出的定义 : 树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。

紫书上差不多也是这样介绍的，很好理解的概念，这道题就是求树的重心的裸题，给定一颗无根树，将每一个点都设置为根，跑一下dfs，更新自己最大的子数具有的节点数（假定生成的子树中还包含祖先），在这些最大值中选取一个最小值，那个节点就是树的重心。

用num[i] 保存自己所有除祖先以外所有子树的节点总和，dp[i]保存所有子树中最大的子树的节点数，再配合链式前向星建图，挺完美的了。建图时还是按照无向图原则敲，遇到祖先就跳过。。。

看了kuangbin大佬的思路之后盲敲了一下子，顺带复习一下链式前向星

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
#define inf 0x3f3f3f3f
int dp[20005];
int head[20005];
int num[20005];
int cnt;
int n;
struct node
{int to;int next;
}a[40005]; // 无向图建两倍边
void init()
{memset(dp, 0, sizeof(dp));memset(head, -1, sizeof(head));cnt = 0;
}
void addedge(int u, int v)
{a[cnt].to = v;a[cnt].next = head[u];head[u] = cnt ++;
}
void dfs(int cur, int fa)
{num[cur] = 1;for(int i = head[cur]; ~ i; i = a[i].next){int v = a[i].to;if(v == fa) continue;dfs(v, cur);dp[cur] = max(dp[cur], num[v]);num[cur] += num[v];}dp[cur] = max(dp[cur], n - num[cur]);
}
int main()
{int t;scanf("%d",&t);while(t --){init();scanf("%d",&n);int u, v;for(int i = 1; i < n; i ++){scanf("%d%d",&u,&v);addedge(u, v);addedge(v, u);}dfs(1, -1);int point;int ans = inf;for(int i = 1; i <= n; i ++){if(dp[i] < ans){point = i;ans = dp[i];}}printf("%d %d\n",point, ans);}return 0;
}