目录
这是一道树的直径题。
首先，树的直径定义是：树上两个结点之间的最短（加权）路中最长的一条路径（和二分答案没关）
但由于贪心思想，这个路径一定起点终点是两片叶子结点
如图，这棵树的直径就是5，即节点3和节点4之间的最短路径
那么，求树的直径有啥方法？
方法一：找每个节点的最长链与次长链之和的最大值
这是代码[code] // 树的直径 dp实现; // https://blog.csdn.net/qq_42211531/article/details/86579115// dp[0]: 结点u的最长儿子链// dp[1]: 结点u的次长儿子链 #include #include #include using namespace std;int const MAX = 100005;int head[MAX], dp[MAX][2];int n, s, cnt, ans; struct EDGE{ int v, w, next;}e[MAX]; void Add(int u, int v, int w){ e[++cnt].v = v; e[cnt].w = w; e[cnt].next = head; head = cnt;}// 利用孩子的最长链去更新父亲的最长链和次长链 void DFS(int u, int fa){ //dp[0]:最长子链； dp[1]:次长子链 dp[0] = dp[1] = 0; for(int i = head; i ; i = e.next) { int v = e.v; int w = e.w; if(v != fa) { DFS(v, u); if(dp[0] < dp[v][0] + w) // 父亲u的最长 < 孩子v的最长 + （u,v）边长 { dp[1]= dp[0]; dp[0] = dp[v][0] + w; } else if(dp[1] < dp[v][0] + w) dp[1] = dp[v][0] + w; } } //枚举经过每个节点的长链，是否最大？ ans = max(ans, dp[1] + dp[0]);} int main(){ memset(head, 0, sizeof(head)); scanf("%d", &n); for(int i = 1; i 4这条</p>可见，树的直径不一定经过根节点！
方法二：先找距离根节点最远的点，再找距离这个点最远的点（2次dp）
这是代码[code] //https://blog.csdn.net/Rainfoo/article/details/105290837//图论-树-最长链（树的直径） #include#include#include#include#includeusing namespace std;#define ll long longconst int maxn=2e5+5;int d[maxn],head[maxn],f_num,ans,tot;struct E{ int to,next,w;}edge[maxn];void add(int u,int v,int z){ edge[tot].to=v; edge[tot].w=z; edge[tot].next=head; head=tot++;}void dfs(int x,int fa){ if(ans>n>>m; for(int i=1;i>u>>v; //cin>>w; add(u,v,w);add(v,u,w); } dfs(1,0); ans=0; d[f_num]=0; dfs(f_num,0); coutf2[sum]) f2[sum]=f1+1; } int ans=-1; for(int i=1;i让孩子的孩子看守孩子的花费）</p> 这时候必须要强制把一个孩子拉出来干活，即fake
这是代码[code] // 皇宫看守 loj 10157 // https://www.cnblogs.com/Forever-666/p/11234958.html #include#include#include#includeusing namespace std;const int MAXN=2200;struct E{int x,y,next;}mm[MAXN |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
