目录

1，树的直径

（1）基本介绍以及方法

（2）例题详解

问题描述

输入格式

输出格式

样例输入

样例输出

评测数据规模

代码详解：

2，树的重心

（1）基本介绍

（2）具体代码详解：

如何求解树的重心：跑一遍dfs，如果mss[x]<=n/2，则x是重心反之不是

注：本文题目均来自蓝桥杯官网公开题目，仅用于技术讨论和算法学习。

1，树的直径

（1）基本介绍以及方法

 树的直径：是树上最长的一条链，当然这条链不唯一，所以一棵树可能有多条链
/*树：无环的连通无向图，任意两点间有且仅有一条路径。
路径长度：路径上的边数（或边权之和，若树为带权树）。
树的直径：树中所有点对路径长度的最大值。
示例：对于一棵普通的二叉树，其直径可能是从某个叶子节点到另一个叶子节点的最长路径，
不一定要经过根节点。*/
 直径由两个顶点u，v决定，若有一条直径(u,v),则满足：1，u，v的度数均为1
 1. 节点的度数（Degree of a Node）
定义：树中某个节点所连接的边的数量，记为deg(v)。
示例：在二叉树中，叶子节点的度数为 1（仅连接父节点），
内部节点的度数通常为 2（连接左右子节点和父节点）。
 2，在以任意一个点为根的树上，u，v,中必然存在一个点作为最深的叶子节点
 注：深度——点距离根节点的距离（从0开始）
 3，如何求树的直径？法一：树状dp
 法二：跑两遍dfs：由于直径端点u，v必然存在一个深度最深的点，那么我们可以在以任意节点为根的树上
 跑一次以1为根dfs求所有点的深度，选取深度最大的点（即max dep1[i],可能有多个，任选一个）作为u
 然后以u为根再跑一次dfs，此时深度最大的点（即nax depu[i],可能有多个，任选一个）就是v
 用max(depu[i],depv[i])来表示最长路径
 or：其长度就是路径上点的个数，等于以u为根的树的dep[v]+1

（2）例题详解

蓝桥杯官网——卖树

问题描述

小蓝和小桥是两位花园爱好者，她们在自己的花园里种了一棵 n 个节点的树，每条边的长度为 k。初始时，根节点为 1 号节点。她们想把这棵树卖掉，但是想卖个好价钱。树的价值被定义为根节点到所有节点的路径长度的最大值。

为了让这棵树更有价值，小蓝和小桥可以对这棵树进行一种操作：花费 c 的代价，将根节点从当前的节点移动到它的一个相邻节点上。注意，这个操作不会改变树的形态，只是改变了根节点的位置。

她们希望通过尽可能地进行操作，使得卖出去的这棵树的盈利最大。盈利被定义为卖出去的树的价值减去操作的总代价。

请你帮助她们，找出她们能够获得的最大盈利。

输入格式

第一行包含一个整数 t，表示测试数据组数。

每组数据第一行包含三个整数 n、k 和 c，表示树的节点数、每条边的长度和进行一次移动操作的代价。

接下来 n−1 行，每行描述树的一条边，包含两个整数 ui 和 vi​，表示树中连接 ui​ 和 vi​ 之间的一条边。

输出格式

对于每组数据，输出一个整数，表示最大盈利。

样例输入

1
3 4 5
1 2
1 3

样例输出

4

评测数据规模

对于 100% 的评测数据，1≤t≤20,2≤n≤105,1≤k,c≤109,1≤ui,vi≤n1≤t≤20

代码详解：

#include <iostream>
#include<vector>
using namespace std;
using ll=long long;
const int N=2e5+9;
ll dep1[N],depu[N],depv[N];//分别表示以1，u，v为根节点的每个节点的深度
//计算深度的函数：需要该节点，父节点，以及深度数组
//本体采用遍历两边dfs的方法，找到最长的链
//利润=（最长的一条链）*k-（以1为起点的最长链，即以1为根深度最大的点到1的距离）*c
vector<int>g[N];
void dfs(int a,int fa,ll dep[])
{
  dep[a]=dep[fa]+1;
  for(const auto&y:g[a])
  {
    if(y==fa) continue;
    dfs(y,a,dep);
  }
}

void solve()
{
  ll n,k,c;cin>>n>>k>>c;
  for(int i=1;i<n;i++)
  {
    int x,y;cin>>x>>y;
    g[x].push_back(y),g[y].push_back(x);
  }
  //初始化dep！让根节点的父节点编号为-1，使得dep[1]=dep[0]+1=0(根节点深度为0)
  dep1[0]=depu[0]=depv[0]=-1;
  //先以编号1的节点为根节点，遍历选出深度最大的节点
  dfs(1,0,dep1);
  //以1为根遍历深度最大的点，将其设为u
  int u=1;
  for(int i=1;i<=n;i++)
  {
    if(dep1[i]>dep1[u]) u=i;
  }
  //再以u为根节点遍历深度最大的节点，设为v，此时树中最长的链必然是u-->v
  //即depu和depv中最大的一条！
  dfs(u,0,depu);//默认所有根的父节点都是0
  int v=1;
  for(int i=1;i<=n;i++)
  {
    if(depu[i]>depu[v]) v=i;
  }
  //别忘了计算depv;
  dfs(v,0,depv);
  ll ans=0;
  for(int i=1;i<=n;i++)
  {
    ans=max(ans,max(depu[i],depv[i])*k-dep1[i]*c);
  }
  cout<<ans<<'\n';
  //清除图，待下一次测试样例
  for(int i=1;i<=n;i++)
  {
    g[i].clear();
  }
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int t;cin>>t;
  while(t--)
  {
    solve();
  }
  return 0;
}

2，树的重心

（1）基本介绍

 树的重心：是指对于某个点，将其删除后可以使得剩余联通块的最大值最小的点
 等价于：以某个点为根的树，将根删除后，剩余的若干个子树的大小的最大值最小
 另一种说法：或是其他点到该点的权值之和最小（下面不提了）
 用mss[x]表示x点的所有子树的大小的最大值（就是子树所含节点的最大值）
 性质：

         1，重心的若干子树的大小一定<=n/2.    n:总结点。除了重心以外的所有其他点，都必然存在一棵节点个数>=n/2的子树。
         2，一棵树最多两个重心，如果存在两个重心，则必然相邻，将链接两个重心的边删除后，一定划分为两棵大小相等的树。
         3.树中所有点的距离到某个点的距离和，到重心的距离和是最小的，若有两个重心，则二一样。
         4.把；两棵树通过一条边相连得到一棵新的树，则新的重心在较大的一棵树一侧的连接点与重心之间的简单路径上，如果两棵树大小一样，则重心就是两个连接点。

（2）具体代码详解：

如何求解树的重心：跑一遍dfs，如果mss[x]<=n/2，则x是重心反之不是

void dfs(int x, int fa)
{
	// 初始化当前节点x的子树大小为1（仅包含自身）
	// mss[x]记录将节点x删除后，最大子树的节点数
	sz[x] = 1, mss[x] = 0;
	// 遍历节点x的所有邻接节点y
	for (const auto& y : g[x])
	{
		// 如果邻接节点y是父节点fa，则跳过（避免重复访问）
		if (y == fa) continue;
		// 递归处理子节点y，其父节点为x
		dfs(y, x);
		// 更新当前节点x的子树大小，加上子节点y的子树大小
		sz[x] += sz[y];
		// 更新mss[x]：记录子树中最大的节点数
		mss[x] = max(mss[x], sz[y]);
	}
	// 考虑删除节点x后，剩余部分（父节点方向的子树）的节点数
	mss[x] = max(mss[x], n - sz[x]);
	// 如果节点x满足重心条件（删除后所有子树的最大节点数不超过总节点数的一半）
	// 则将其加入重心列表v
	if (mss[x] <= n / 2) v.push_back(x);
}
/*为什么递归调用必须在中间？
计算子树大小：
在树的 DFS 中，要计算当前节点x的子树大小sz[x]，必须先递归计算所有子节点y的子树大小sz[y]，
然后将它们累加起来（sz[x] += sz[y]）。所以要先遍历所有子树，直到没有子树，再依次往上加
如果递归调用放在后面，sz[y]的值将是未初始化的（通常为 0），导致sz[x]计算错误。
更新最大子树大小：
mss[x]记录删除节点x后最大子树的节点数。这需要先知道所有子树的大小（通过递归调用获取），
才能比较得出最大值。如果递归调用放在后面，子树的信息尚未计算，mss[x]会得到错误结果。*/

        OK了，觉得不错，不妨点赞+关注+收藏吧！！！