首页 > 其他分享 >19031 树的重心

19031 树的重心

时间:2024-09-01 21:54:12浏览次数:14  
标签:连通 重心 int max subtree size 节点 19031

### 思路
1. 使用DFS遍历树,计算每个节点的子树大小。
2. 计算每个节点的最大连通块大小。
3. 找到最大连通块大小最小的节点,即为树的重心。

### 伪代码
1. 读取输入数据,构建树的邻接表。
2. 定义DFS函数,计算每个节点的子树大小。
3. 遍历所有节点,计算每个节点的最大连通块大小。
4. 找到最大连通块大小最小的节点,输出结果。

### C++代码
 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100000 + 5;
vector<int> adj[MAXN];
int subtree_size[MAXN];
int max_subtree[MAXN];
int n;

void dfs(int u, int parent) {
    subtree_size[u] = 1;
    max_subtree[u] = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);
        subtree_size[u] += subtree_size[v];
        max_subtree[u] = max(max_subtree[u], subtree_size[v]);
    }
    max_subtree[u] = max(max_subtree[u], n - subtree_size[u]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, -1);

    int min_max_subtree = n;
    vector<int> centroids;
    for (int i = 1; i <= n; ++i) {
        if (max_subtree[i] < min_max_subtree) {
            min_max_subtree = max_subtree[i];
            centroids.clear();
            centroids.push_back(i);
        } else if (max_subtree[i] == min_max_subtree) {
            centroids.push_back(i);
        }
    }

    sort(centroids.begin(), centroids.end());
    for (int centroid : centroids) {
        printf("%d ", centroid);
    }
    printf("\n");

    return 0;
}

### 细节
1. 使用邻接表存储树的结构。
2. 使用DFS计算每个节点的子树大小和最大连通块大小。
3. 遍历所有节点,找到最大连通块大小最小的节点。
4. 输出结果时,若有多个重心,按节点编号从小到大输出。

标签:连通,重心,int,max,subtree,size,节点,19031
From: https://blog.csdn.net/huang1xiao1sheng/article/details/141639425

相关文章

  • 树的重心
    树的重心性质:一个点是重心,等价于,以这个点为根,它的每个子树的大小,都不会超过整个树大小的一半(充要条件)性质及其证明POJ3107模板这题卡vector注意判断数组越界voiddfs(inti,intfa){ siz[i]=1; inttmp=0; for(intj=head[i];~j;j=e[j].next){ intv=e[j].to; if(v!......
  • 通达信心理重心战术副图指标公式源码
    {通达信心理重心战术副图指标公式源码}N:=12;{参数可以自己调整}stICKLINE(1,100,100,10,0),COLOR0099FF;STICKLINE(1,0,0,10,0),COLOR0099FF;STICKLINE(1,80,80,1.5,0),COLORYELLOW;STICKLINE(1,20,20,1.5,0),COLORYELLOW;STICKLINE(1,50,50,0.7,0),COLORWHITE;MID:=(......
  • 中心 重心
    中心重心重心 和 中心 是两个不同的概念,但在某些情况下可以互换使用。以下是它们的定义和使用场景:重心:在数学和物理学中,重心是指一个图形或物体的几何中心点,它位于所有边或面(如果有的话)的质心位置。对于三角形来说,重心是位于三条边上的中线交点。在更复杂......
  • 重心的意思是指代事、物的核心或主要部分。
    重心的意思是指代事、物的核心或主要部分。一、重心的多种释义1、在日常语言中重心通常用来指代事物的核心或主要部分,例如“工作的重心”或“问题的重心”。2、在物理上重心是指物体各部分所受重力的合力的作用点。质量分布均匀的物体(均匀物体),重心的位置只跟物体的形状有关。......
  • 重心法判断点是否在三角形内
    1)点在三角形的边上时AP=AE+AF(向量加法)设AE=v*AB,AF=u*AC; 则AP=v*AB+u*AC(二元一次方程,u,v为我们引入的变量)根据向量三点共线定理可知:u+v=1 2) 点在三角形内时AE不变, 让AF变短一些, 当用u*AC表示AF时,u的值肯定也比1)中小了,所以此时u+v<1 所以点是否在三......
  • 数学基础:三角形重心坐标插值公式的证明
    在快速Phong明暗处理(Blinn-Phong明暗处理)时,出现了三角形重心坐标插值公式,但没有给出证明.网上也鲜有证明过程,这里给出证明.问题描述:在三角形ABC中,三顶点A、B、C坐标分别为\((x_1,y_1,z_1)、(x_2,y_2,z_2)、(x_3,y_3,z_3)\).则三角形内任一点P(x,y,z)可表示为:\[\tag{1}P=\alph......
  • P5666 [CSP-S2019] 树的重心
    考虑一个结点在什么情况下会成为重心。随便钦定一个根结点。对于结点\(u\),假设割掉了其子树\(v\)中的某条边或连接\(u\)和\(v\)的边,形成了一棵大小为\(k\)的新树。令\(mx\)表示除\(v\)子树外最大的子树大小(或\(n-siz_u\))。如果\(u\)成为了重心根据定义有\(2\ti......
  • 关于三角形的四种心(外心,内心,重心,垂心)
    外心三条边垂直平分线的交点为外心。到三顶点距离相等内心三条内角平分线的交点为内心。到三条边的距离相等同时是内切圆的圆心重心三条中心的交点为重心同时是物理意义上的重心公式:\(G(x_0,y_0),x_0=\frac{x_1+x_2+x_3}{3},y_0=\frac{y_1+y_2+y_3}{3}\)垂心......
  • 树的直径、重心、中心
    树的直径、重心、中心一、树的直径我们将一棵树\(T=(V,E)\)的直径定义为$max(u,v)(u,v∈V)$,即树中所有最短路径距离的最大值即为树的直径。求法:1)树形dp定义d1为从节点u到其子树中节点距离的最大值,d2为次大值,则\(diameter=max(d1+d2)\)特点:不可输出路径,但可以处理负边......
  • [CSP-S2019] 树的重心 题解
    [CSP-S2019]树的重心因为这道题令我十分兴奋,所以来写一下做完后的思考。这道题用到了树的重心的种种性质,在写解法的时候会一一点出其用处。首先,枚举每一条边,然后各自\(O(n)\)扫一次的\(O(n^2)\)做法是简单的。那么接下来,就会出现不同的解法了:优化\(O(n)\)求解的过程......