路径相关树形dp——最长乘积链

路径相关树形dp——最长乘积链

问题描述

给定一棵树,树中包含n个结点,编号为1~n,以及n- 1条无向边,每条边都有一个权值。

现从树中任选一个点, 从该点出发,在不走回头路的情况下找出二条到其他点的路径,这二条路径不能有公共边,请问这二条路径长度的乘积最大可以是多少。

注:如果从该点出发只有一个方向可以走,换句话说该点入度出度为1,则乘积为0。

输入格式

第一行输入一个整数n。

接下来n- 1行,每行输入包含三个整数 a i , b i , c i a_i,b_i,c_i ai,bi,ci,表示点 a i a_i ai b i b_i bi之间存在一条权值为 c i c_i ci的边。

输出格式

输出一个整数,为1二条路径长度乘积的最大值。

题目分析

考虑对于一个节点i而言,它的最长链要怎么去寻找,我们还是要画图看一下,就拿之前的那张图吧。

在这里插入图片描述

对于节点4而言,寻找它的最长链首先有两个寻找方向,向下沿着儿子节点寻找一条最长链和向上沿着父节点寻找一条最长链,那么次长链呢?我只有一个寻找方向,就是向下沿着儿子节点寻找,并且这个儿子节点不能在最长链里面,为什么不能向上沿着父节点寻找呢?因为向上寻找必然经过父节点,但是向上找最长链时父节点已经在了,两条链不能有重复的节点。

接下来看怎么求,先看向下沿着儿子节点寻找一条最长链和次长链怎么求。通过一次dfs可以求出来,代码如下,注意在求最长链和次长链的同时,也要记录他们是沿着哪个儿子节点的链。dp1[u]表示节点u向下走的最长链的大小,p1[u]表示最长链是沿着哪个儿子节点走的,dp2[u]表示节点u向下走的次长链的大小,p2[u]表示次长链是沿着哪个儿子节点走的。假设儿子节点是e,那么节点u沿着节点e的最长链用dp1[e]+w表示,w代表u和e之间的距离。然后用dp1[e]+w和现在的dp1[u]比较,如果dp1[u]小,则更新dp1[u],同时将现在的dp1[u]的值给dp2[u]。否则看dp1[e]+w和现在的dp2[u]的大小,如果dp2[u]小,用dp1[e]+w更新dp2[u]。注意在更新dp1[u]和dp2[u]的同时也要更新对应的p1[u]和p2[u]。代码如下,

private static void dfs1(int u, int fa) {if(map.get(u)==null) return;for(node e:map.get(u)) {int v = e.x;if(v==fa) continue;dfs1(v, u);if(dp1[v]+e.w>dp1[u]) {dp2[u]=dp1[u];p2[u]=p1[u];dp1[u]=dp1[v]+e.w;p1[u]=v;}else if(dp1[v]+e.w>dp2[u]) {dp2[u]=dp1[v]+e.w;p2[u]=v;}}
}

现在看怎么求向上沿着父节点寻找一条最长链,节点到父节点的距离为w,加上父节点向下走的最长链与向上走的最长链的最大值,但是这里要注意,如果父节点的最长链是沿着该节点走的,则不能用,要更改为加上父节点向下走的次长链与向上走的最长链的最大值,这里也体现了为什么要有数组p1和p2,代码如下

private static void dfs2(int u, int fa) {if(map.get(u)==null) return;for(node e:map.get(u)) {int v = e.x;if(v==fa) continue;		if(p1[u]==v) {up[v] = e.w+Math.max(up[u], dp2[u]);}else {up[v] = e.w+Math.max(up[u], dp1[u]);}dfs2(v, u);}
}

现在我们需要的东西都求出来了,题目要求次长链和最长链的乘积最大值,那么也就是向下走的最长链乘以向下走的次长链的乘积与向下走的最长链乘以向上走的最长链的乘积里取一个最大值,代码如下

for(int i = 1;i <= n;i++) {res = Math.max(Math.max((long)dp1[i]*up[i], (long)dp1[i]*dp2[i]), res);
}
题目代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
public class Main{static class node{int x,w;public node(int x, int w) {super();this.x = x;this.w = w;}}static HashMap<Integer, List<node>> map = new HashMap<Integer, List<node>>();static int dp1[],dp2[],up[],p1[],p2[];
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();dp1 = new int[n+1];dp2 = new int[n+1];up = new int[n+1];p1 = new int[n+1];p2 = new int[n+1];for(int i = 1;i < n;i++) {int u = scanner.nextInt();int v = scanner.nextInt();int c  =scanner.nextInt();add(u,v,c);add(v,u,c);}dfs1(1,0);dfs2(1,0);long res = 0;for(int i = 1;i <= n;i++) {res = Math.max(Math.max((long)dp1[i]*up[i], (long)dp1[i]*dp2[i]), res);}System.out.println(res);
}
private static void dfs2(int u, int fa) {if(map.get(u)==null) return;for(node e:map.get(u)) {int v = e.x;if(v==fa) continue;if(p1[u]==v) {up[v] = e.w+Math.max(up[u], dp2[u]);}else {up[v] = e.w+Math.max(up[u], dp1[u]);}dfs2(v, u);}
}
private static void dfs1(int u, int fa) {if(map.get(u)==null) return;for(node e:map.get(u)) {int v = e.x;if(v==fa) continue;dfs1(v, u);if(dp1[v]+e.w>dp1[u]) {dp2[u]=dp1[u];p2[u]=p1[u];dp1[u]=dp1[v]+e.w;p1[u]=v;}else if(dp1[v]+e.w>dp2[u]) {dp2[u]=dp1[v]+e.w;p2[u]=v;}}
}
private static void add(int u, int v, int c) {if(!map.containsKey(u)) map.put(u, new ArrayList<node>());map.get(u).add(new node(v, c));
}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/260382.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

keil5代码复制下来中文乱码

在keil5中&#xff0c;显示正常&#xff0c;如果复制到其他编辑器&#xff0c;中文部分就乱码。 keil5中显示正常 复制到其他编辑器&#xff0c;中文乱码。 原因&#xff1a;编码格式不一样 解决办法&#xff1a;keil5中重新设置一下。 左边选择Edit&#xff0c;下面选择Conf…

第3.3章:StarRocks数据导入--Stream Load

一、概述 Stream Load是StarRocks常见的数据导入方式&#xff0c;用户通过发送HTTP请求将本地文件或数据流导入至StarRocks中&#xff0c;该导入方式不依赖其他组件。 Stream Load作是一种同步导入方式&#xff0c;可以直接通过请求的返回值判断导入是否成功&#xff0c;无法手…

考PMP真的有用吗?

在你决定考证之前&#xff0c;值得思考的是为什么要追求这个证书。是因为公司的需求&#xff1f;个人职业发展&#xff1f;还是受到了新闻报道或广告的影响&#xff0c;觉得PMP证书有价值&#xff0c;只是出于好奇想了解一下。这种情况下&#xff0c;很多人可能会表示&#xff…

idea代码review工具Code Review Helper使用介绍

之前在团队里面遇到一个关于代码review的问题&#xff0c;使用gitlab自己的还是facebook的Phabricator&#xff0c;很难看到整体逻辑&#xff0c;因为业务逻辑代码可能不在这次改动范围内&#xff0c;在去源库中找不好找。针对这个刚需&#xff0c;在网上找了一个idea的代码工具…

设计模式简介

设计模式介绍: 设计模式是对大家实际工作中写的各种代码进行高层次抽象的总结&#xff0c;其中最出名的当属 Gang of Four&#xff08;GoF&#xff09;的分类了&#xff0c;他们将设计模式分类为 23 种经典的模式&#xff0c;根据用途我们又可以分为三大类&#xff0c;分别为创…

openGauss 5.0.0全密态数据库应用小试

前言 openGauss HCIA教材中&#xff0c;安全是一个重要的章节&#xff0c;在实际项目中&#xff0c;随着网络安全和信息安全形势的变化&#xff0c;企业也越来越重视数据库安全。去年在HALP内部进行openGauss培训时&#xff0c;安全特性就被学员们提出来要重点讲解&#xff0c…

如何使用Docker搭建YesPlayMusic网易云音乐播放器并发布至公网访问

文章目录 1. 安装Docker2. 本地安装部署YesPlayMusic3. 安装cpolar内网穿透4. 固定YesPlayMusic公网地址 本篇文章讲解如何使用Docker搭建YesPlayMusic网易云音乐播放器&#xff0c;并且结合cpolar内网穿透实现公网访问音乐播放器。 YesPlayMusic是一款优秀的个人音乐播放器&am…

Pandas数据库大揭秘:read_sql、to_sql 参数详解与实战篇【第81篇—Pandas数据库】

Pandas数据库大揭秘&#xff1a;read_sql、to_sql 参数详解与实战篇 Pandas是Python中一流的数据处理库&#xff0c;而数据库则是数据存储和管理的核心。将两者结合使用&#xff0c;可以方便地实现数据的导入、导出和分析。本文将深入探讨Pandas中用于与数据库交互的两个关键方…

【Go语言】Go项目工程管理

GO 项目工程管理&#xff08;Go Modules&#xff09; Go 1.11 版本开始&#xff0c;官方提供了 Go Modules 进行项目管理&#xff0c;Go 1.13开始&#xff0c;Go项目默认使用 Go Modules 进行项目管理。 使用 Go Modules的好处是不再需要依赖 GOPATH&#xff0c;可以在任意位…

JS逆向进阶篇【去哪儿旅行登录】【中篇-滑动轨迹破解补浏览器环境破参数】

目录&#xff1a; 每篇前言&#xff1a;0、整体分析1、逆向轨迹snapshot&#xff08;1&#xff09;分析&#xff1a;&#xff08;2&#xff09;Python轨迹生成&#xff1a;&#xff08;3&#xff09;AES加密&#xff1a;&#xff08;4&#xff09;轨迹加密&#xff1a;&#xf…

机器学习中梯度下降法的缺点

机器学习中的梯度下降法是一种寻找函数最小值的优化算法&#xff0c;广泛应用于训练各种模型&#xff0c;尤其是在深度学习中。尽管其应用广泛&#xff0c;但梯度下降法也存在一些不可忽视的缺点&#xff1a; 1. 局部最小值和鞍点 局部最小值问题&#xff1a; 对于非凸函数&a…

milvus insert数据在s3的存储

insert数据在s3的存储 对segment进行flush操作&#xff0c;会将数据持久化至s3对象存储。 相关核心代码位置: ibNode.flushManager.flushBufferData()主要代码在flushBufferData()函数。 代码位置:internal\datanode\flush_manager.go // flushBufferData notifies flush …

【Docker】Docker存储卷

文章目录 一、什么是存储卷二、为什么需要存储卷三、存储卷分类四、管理卷Volume创建卷方式一&#xff1a;Volume 命令操作方式二&#xff1a;-v 或者--mount 指定方式三&#xff1a;Dockerfile 匿名卷 操作案例Docker 命令创建管理卷Docker -v 创建管理卷Docker mount 创建管理…

java中容易被忽视的toString()方法

之前一直认为toString就是将数据转换成字符类型&#xff0c;直到最近写出了一个bug才对toString有了新的认识 不同数据类型&#xff0c;toString() 有不同的操作 定义一个student类&#xff0c;包含姓名 String类型、性别 String类型、年龄 int 类型、分数列表 String类型的li…

适合tiktok运营的云手机需要满足什么条件?

TikTok作为一款全球热门的社交媒体平台&#xff0c;具有无限的市场潜力。然而&#xff0c;卖家在运营过程中常常会面临到视频0播、账号被降权、限流等问题&#xff0c;甚至可能因为多人同时使用一个IP而导致封号的风险。为了规避这些问题&#xff0c;越来越多的卖家将目光投向了…

论UI的糟糕设计:以百度网盘为例

上面这一排鼠标一经过就会弹出来&#xff08;不是点才弹出来&#xff09;&#xff0c;然后挡住你的各种操作&#xff0c; 弹出来时你就必须等它消失&#xff0c;卡一下才能操作。 在用户顺畅地操作内容时&#xff0c;经常就卡一下、卡一下、卡一下…… 1、比如鼠标从下到上&am…

《基于CEEMDAN一小波包自适应阈值混凝土声发射信号降噪研究》算法思路笔记

![1]杨智中,林军志,汪魁等.基于CEEMDAN-小波包自适应阈值混凝土声发射信号降噪研究[J].振动与冲击,2023,42(03):139-149.DOI:10.13465/j.cnki.jvs.2023.03.016.](https://img-blog.csdnimg.cn/direct/9814ff64cc474cd3aa06ecaea60f2f75.png) 首先对周期循环荷载作用下混凝土试…

【RPG Maker MV 仿新仙剑 战斗场景UI (二)】

RPG Maker MV 仿新仙剑 战斗场景UI 二 战斗指令菜单原仙剑战斗指令图RMMV战斗指令对应代码战斗指令菜单代码效果 战斗指令菜单 原仙剑战斗指令菜单是使用方向键控制&#xff0c;同时按照使用情况正好对应四个指令和四个方向&#xff0c;同时没有选中的菜单用黑色透明图片覆盖&…

App启动优化笔记 1

app大致的启动流程。有Launcher进程,system_server进程,zygote进程,APP进程。 Launcher进程:启动activity来启动应用 system_server进程:(ams是其中的一个binder):发送一个socket消息给Zygote。 zygote进程:收到消息后,fork新的进程,---》app进程启动 APP进程:…

国际语言代码 Language Code 对照表速查

前言 语言代码是英国教育社会学家伯恩斯坦的术语。指在一定的语言集团中&#xff0c;特定的人群在特定的社会环境下使用的特定的言语。分为限定代码&#xff08;restricted code&#xff09;和精制代码&#xff08;elaborated code&#xff09;。语言代码是由字母或数字组成的…