树直径和树重心

冷不防 2023-06-12 04:24 19阅读 0赞

主要是留个板子

因为我似乎不会证明

树直径

丛树的任一点开始找一个离该节点最远的点，该点必为树直径的一端点，再从该点出发找最远点即为树直径

方法：dfs 时间O(2n)

树重心

以某个节点为树根，最大子树最小的节点

方法是树dp 时间O(n)

要注意的点都在代码注释里

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll INF=0x3f3f3f;
    const int N=5e5+7;
    int dp[N];///存该节点不走父边的所有节点和
    vector<int>son[N];///vector邻接表存树
    int mi;///最大子树最小值
    int n,m;
    int a[N];///以下标为节点的树的最大子树节点数
    void dfs(int x,int fa)
    {
        dp[x]=1;
        a[x]=0;
        for(int i=0;i<son[x].size();i++)
        {
            if(son[x][i]==fa) continue;
            dfs(son[x][i],x);
            dp[x]+=dp[son[x][i]];
            a[x]=max(a[x],dp[son[x][i]]);
        }
        a[x]=max(a[x],n-dp[x]);
        if(a[x]<mi) mi=a[x];
    
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin>>n;
        m=n-1;
        mi=n;
        while(m--)
        {
            int a1,a2;
            cin>>a1>>a2;
            son[a1].push_back(a2);
            son[a2].push_back(a1);
        }
        dfs(1,0);
        for(int i=1;i<=n;i++)
            if(a[i]==mi)
            cout<<i<<' ';cout<<endl;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关树的直径

树的直径 * 前言 * 源代码 * 参考博客前言路径：一棵树上，任意两个节点之间最多有一条简单路径。我们用 dis(a,b)表示点a和...

- 日理万妓/ 2024年04月17日 18:24/ 0 赞/ 85 阅读

相关【树的直径】树上子链

[F-树上子链\_牛客竞赛动态规划专题班树型dp例题 (nowcoder.com)][F-_dp_ _nowcoder.com] 题意： ![39c6a6eb334648c

秒速五厘米/ 2024年03月22日 17:39/ 0 赞/ 88 阅读

相关树的重心专题

解题思路：选择一个节点作为根，设dp\[i\]表示以i为根的树的总节点个数，dp\[i\]=满足j为其子节点的的d\[j\]之和再加1（根节点）。只需在dfs过程中找到最大的子

清疚/ 2023年08月17日 16:26/ 0 赞/ 128 阅读

相关树的重心

树的重心 > 说明：下面的定义等都是按照个人的理解所表述的，如有错误欢迎批评指出。 1.定义：去掉该节点，最大的连通块（子树）的节点数目最少，则该节点点称作该树

红太狼/ 2023年07月10日 08:22/ 0 赞/ 19 阅读

相关树直径和树重心

主要是留个板子因为我似乎不会证明树直径丛树的任一点开始找一个离该节点最远的点，该点必为树直径的一端点，再从该点出发找最远点即为树直径方法：dfs 时间O(2n)

冷不防/ 2023年06月12日 04:24/ 0 赞/ 20 阅读

相关树的重心

题目描述给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。重心定义：重心是指树中的一

浅浅的花香味﹌/ 2022年10月25日 15:27/ 0 赞/ 182 阅读

相关 Leetcode 543. 二叉树的直径(直径 = 左子树高度 + 右子树高度)

题目重述给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。示例 : 给定二叉树

我不是女神ヾ/ 2022年09月02日 11:38/ 0 赞/ 196 阅读

相关树的直径

树的直径树上最长的简单路径即为树的直径。求树的直径的方法就是在树上任选一点u，求距离点u最远的点v，再求距离点v最远的点s，点u到点s的距离即为树的直径。（即两遍D

约定不等于承诺〃/ 2022年05月12日 11:04/ 0 赞/ 201 阅读

相关 SDOI2013 直径（树的直径必经边）

SDOI2013 直径 [题目传送][Link 1] sol: 先求出任一直径同时把直径拎出来，树的非直径部分全部挂在直径上（如下）。 ![a][] 对于直径上的

- 日理万妓/ 2021年11月23日 23:12/ 0 赞/ 324 阅读

相关 HDU 6567 Cotree 树的重心（树的重心）

题意：给定n的点，n-2条边，也就是给出了两棵树，要求加一条边连接两棵树并使得连接好的这棵树上任意两点距离和最小。分析：树的重心一个很重要的性质就是所有点到当前点的距

川长思鸟来/ 2021年10月18日 07:48/ 0 赞/ 278 阅读