太平洋建设21局网站,wordpress安装插件要求ftp,商务网站底部设计,三明网站开发树的重心是指对于某个点#xff0c;将其删除后#xff0c;可以使得剩余联通块的最大值最小。也就等价于一某个点为根的树#xff0c;将根删除后#xff0c;剩余的若干棵子树的大小最小。
例如下图的树的重心就是2。 性质#xff1a; 性质一#xff1a;重心的若干棵子树打…树的重心是指对于某个点将其删除后可以使得剩余联通块的最大值最小。也就等价于一某个点为根的树将根删除后剩余的若干棵子树的大小最小。
例如下图的树的重心就是2。 性质 性质一重心的若干棵子树打大小一定小于等于 n/2n为总节点个数。除了重心以外的所有其他点都必然存在一棵节点个数大于 n/2 的子树。 性质二一棵树至多有两个重心如果存在两个重心则必然相邻。将脸两个重心的边删除后一定划分为两棵大小相等的树。 性质三树中所有点到重心的距离和是最小的。如果有两个重心那么到他们的距离和一样反之距离和最小的点一定是重心。 求重心的方法
mss[ ]表示x点所有子树大小的最大值即如下图所示其实2的子树大小的最大值为2。 package lanqiao;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;/*** 2024/3/31 10:08*/
public class lanqiao_树的重心 {static int n;static ListInteger[] list;static ListInteger res;static int[] sz;static int[] mss;public static void main(String[] args) {Scanner scannew Scanner(System.in);nscan.nextInt();resnew ArrayList();sznew int[n1];mssnew int[n1];listnew List[n1];for (int i 0; i n 1; i) {list[i]new ArrayList();}for (int i0;in-1;i){int xscan.nextInt();int yscan.nextInt();list[x].add(y);list[y].add(x);}dfs(1,0);System.out.println(该树的重心为);for (int i 0; i res.size(); i) {System.out.print(res.get(i) );}System.out.println();}public static void dfs(int x,int father){sz[x]1;mss[x]0;for (int y:list[x]){if (yfather)continue;dfs(y,x);sz[x]sz[y];//不断找x的各种不同子树mss[x]Math.max(mss[x],sz[y]);//找出x点的子树大小的最大值}mss[x]Math.max(mss[x],n-sz[x]);//比较x的子树和除x及其子树的另一棵树的大小取出最大值if (mss[x]n/2)//应用性质一res.add(x);}
}运行结果
6
5 1
1 4
6 3
2 6
6 1
该树的重心为
6 1 Process finished with exit code 0
