首页 > 其他分享 >树的直径——树形dp求法

树的直径——树形dp求法

时间:2023-12-05 20:55:44浏览次数:37  
标签:int ed dfs 求法 树形 ans d2 dp d1

树上任意两节点之间最长的简单路径即为树的「直径」。

树形 DP的做法 可以在存在负权边的情况下求解出树的直径。

const int N=10010,M=20010;
int n,a,b,c,ans;
struct edge{int v,w;};
vector<edge> e[N];

int dfs(int x,int fa){
  int d1=0,d2=0; 
  for(auto ed : e[x]){
    int y=ed.v, z=ed.w;
    if(y==fa) continue;//这样就不用开vis数组了,节约空间
    int d=dfs(y,x)+z;
    if(d>=d1) d2=d1,d1=d;
    else if(d>d2) d2=d;
  }
  ans=max(ans,d1+d2);
  return d1;//返回从u点往下走的最大长度(悬挂在u点上的最长路径的长度)
}
int main(){
  cin>>n;
  for(int i=1; i<n; i++){
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    e[b].push_back({a,c});
  }
  dfs(1,-1);
  cout<<ans;
}

标签:int,ed,dfs,求法,树形,ans,d2,dp,d1
From: https://www.cnblogs.com/mathiter/p/17878126.html

相关文章

  • LayUI树形结构
    最近在学习LayUI学到tree组件,所以做一下随笔记录下面是我用来接收数据的类namespaceHisProject.Models{publicclassTreeListToReturn{publicstringid{get;set;}publicstringtitle{get;set;}publicList<TreeListToReturn>chil......
  • csp认证202109-4——之状态压缩dp加期望(记忆化搜索
    https://www.acwing.com/problem/content/description/4012/#include<bits/stdc++.h>usingnamespacestd;#definelllonglong//#defineintlonglong#defineullunsignedlonglong#definepiipair<int,int>//#definedoublelongdouble#define......
  • 【组成原理-指令】扩展操作码的树形解法
    仿照哈夫曼树(或前缀编码,Prefix-free)的解法,目前先不解释具体怎么画了,直接放例题,大家自己慢慢品味吧。【例1】某指令系统指令长16位,操作码字段为4位,地址码字段为4位,采用扩展操作码技术,形成三地址指令15条、二地址指令15条、一地址指令15条、零地址指令16条。【解......
  • fpd dpd vintage 滚动率
    滚动率:selecta.loan_month,b.M1/a.Cas'C-M1',c.M2/a.CAS'C-M2',d.M3/a.CAS'C-M3'from(select*fromchenqianguang.GD)asaleftjoin(select*fromchenqianguang.GD)asbona.loan_month=b.loan_monthanda.mob+1=b.mobLE......
  • 【小沐学前端】Node.js实现UDP通信
    1、node简介Node.js是一个开源的、跨平台的JavaScript运行时环境。Node.js是一个开源和跨平台的JavaScript运行时环境。它是几乎任何类型项目的流行工具!Node.js在浏览器之外运行V8JavaScript引擎(GoogleChrome的内核)。这使得Node.js非常高效。Node.js应用在......
  • react项目vite报错:UnhandledPromiseRejectionWarning: SyntaxError: Unexpected toke
    问题:vite报错:UnhandledPromiseRejectionWarning:SyntaxError:Unexpectedtoken'??='今天clone一个vite的项目,安装依赖后运行npmrundev报错:UnhandledPromiseRejectionWarning:SyntaxError:Unexpectedtoken'??='atLoader.moduleStrategy(internal/modules......
  • Qt之UDP多播(组播)的使用
    UdpSocket::UdpSocket(QObject*parent):QObject(parent){//本机IPQStringlocal_ip="192.168.101.11";m_udp_socket=newQUdpSocket(this);connect(m_udp_socket,&QUdpSocket::readyRead,this,&UdpSocket::received_data);......
  • js实现树形结构
    letcityList=[ {id:1,parentId:0,name:'江苏省'}, {id:2,parentId:0,name:'广东省'}, {id:3,parentId:0,name:'安徽省'}, {id:4,parentId:1,name:'苏州市'}, {id:5,parentId:1,name:'无锡市'}, {id:6,parentId:......
  • UDP通信
    一、UDP概述传输层主要应用的协议模型有两种,一种是TCP协议,另外一种则是UDP协议。TCP协议在网络通信中占主导地位,绝大多数的网络通信借助TCP协议完成数据传输。但UDP也是网络通信中不可或缺的重要通信手段。相较于TCP而言,UDP通信的形式更像是发短信。不需要在数据传输之前建立、维......
  • AT_dp
    AT_dp_aFrog1设\(dp_i\)表示从\(1\)跳到\(n\)至少需要多少费用,那么\(i\)只能从\(i-1\)或\(i-2\)跳过来,因此得到\[dp_i=\min\{dp_{i-1}+|a_i-a_{i-1}|,dp_{i-2}+|a_i-a_{i-2}|\}\]时间复杂度\(O(n)\)。#include<bits/stdc++.h>#defineintlonglongusingnam......