树的重心
1.以重心为树根时,所有子树的大小不超过全树大小的一半。
2.树中所有点到某个点的距离和中,重心的距离和是最小的,如果有两个重心,那么到它们的距离和一样。
3.把两棵树通过一条边相连得到一棵新的树,那么新的树的重心在连接原来两棵树的重心的路径上。
4.在一棵树上添加或删除一个叶子,那么它的重心最多只移动一条边的距离。
void getcenter(int u, int fa)
{
size[u] = 1, sub[u] = 0;
for (int i = hd[u]; i; i = g[i].nxt)
{
int v = g[i].to;
if (v == fa)continue;
getcenter(v, u);
size[u] += size[v];
sub[u] = max(sub[u], size[v]);
}
sub[u] = max(sub[u], n - size[u]);
if (sub[u] < sub[center] || (sub[u] == sub[center] && u < center))
center = u;
return;
}
树的直径
性质:在一棵树上距离任何一个点最远的点一定是直径的某一端点。
void dfs(int u, int f)
{
fa[u] = f;
if (dis[u] > dis[far])
far = u;
for (int i = hd[u]; i; i = g[i].nxt)
{
int v = g[i].to, w = g[i].val;
if (v == f) continue;
dis[v] = dis[u] + w;
dfs(v, u);
}
return;
}
dis[1] = 0, dfs(1, 0);
dis[far] = 0, dfs(far, 0);
标签:sub,重心,int,dfs,直径,dis,size From: https://www.cnblogs.com/xqk0225/p/16822244.html