2025/2/15课堂记录
目录[*]数字转换
[*]皇宫看守
[*]数字转换
这是一道树的直径题。
首先，树的直径定义是：树上两个结点之间的最短（加权）路中最长的一条路径（和二分答案没关）
但由于贪心思想，这个路径一定起点终点是两片叶子结点
如图，这棵树的直径就是5，即节点3和节点4之间的最短路径
那么，求树的直径有啥方法？
方法一：找每个节点的最长链与次长链之和的最大值
这是代码 //树的直径 dp实现; //https://blog.csdn.net/qq_42211531/article/details/86579115//dp: 结点u的最长儿子链//dp: 结点u的次长儿子链 #include #include #include using namespace std;int const MAX = 100005;int head, dp;int n, s, cnt, ans; struct EDGE{ int v, w, next;}e; void Add(int u, int v, int w){ e[++cnt].v = v; e.w = w; e.next = head; head = cnt;}// 利用孩子的最长链去更新父亲的最长链和次长链 void DFS(int u, int fa){ //dp:最长子链； dp:次长子链 dp = dp = 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 < dp + w) // 父亲u的最长 < 孩子v的最长 + （u,v）边长 { dp= dp; dp = dp + w; } else if(dp < dp + w) dp = dp + w; } } //枚举经过每个节点的长链，是否最大？ ans = max(ans, dp + dp);} int main(){ memset(head, 0, sizeof(head)); scanf("%d", &n); for(int i = 1; i 4这条</p>可见，树的直径不一定经过根节点！
方法二：先找距离根节点最远的点，再找距离这个点最远的点（2次dp）
这是代码 //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,head,f_num,ans,tot;struct E{ int to,next,w;}edge;void add(int u,int v,int z){ edge.to=v; edge.w=z; edge.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=0; dfs(f_num,0); coutf2]) f2]=f1+1; } int ans=-1; for(int i=1;i让孩子的孩子看守孩子的花费）</p> 这时候必须要强制把一个孩子拉出来干活，即fake
这是代码 // 皇宫看守 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
页:
[1]