search
HomeDatabaseMysql Tutorial树形DP图画入门题解2 (HDU2196)

http://acm.hdu.edu.cn/showproblem.php?pid=2196 题意:一棵树N个节点,每条边有一个权w,求每个节点距离最远的路径长度。 2次深搜: 【第一次深搜】:求出在节点u的子树中,离u的最远,次远距离, 并标记 是从哪儿来的 。 int max_lenth[u] , max_id[u] ;

http://acm.hdu.edu.cn/showproblem.php?pid=2196

题意:一棵树N个节点,每条边有一个权值w,求每个节点距离最远的路径长度。


2次深搜:

 【第一次深搜】:求出在节点u的子树中,离u的最远,次远距离, 并标记是从哪儿来的

int max_lenth[u] , max_id[u] ;      最远距离, 转移儿子节点
int second_lenth[u] , second_id[u] ;  次远距离, 转移儿子节点

树形DP图画入门题解2 (HDU2196)


图1 :  第一次深搜, 当节点1的子树(绿色部分)遍历完回退的时候,最远次远距离只能是从(红色部分)2,6,9过来, 

          转移儿子节点就在2,6,9中选择。  也就是说max_id【1】 , second_id【1】 中存储的是2,6,9 中的某个。



树形DP图画入门题解2 (HDU2196)


图2 :  第一次深搜, 当节点2的子树(绿色部分)遍历完回退的时候,最远次远距离只能是从(红色部分)3,5过来, 

          转移儿子节点就在3,5中选择。  也就是说max_id【2】 , second_id【2】 中存储的是3,5 中的某个。


【第二次深搜】 : 求每个节点在整棵树上的最远、次远距离



树形DP图画入门题解2 (HDU2196)




图3 :  先看状态转移:

          对于节点2 , 最远距离、次远距离,来自2个地方(绿色部分)。

          绿色区域1、 节点2的子树部分,这个在第一次深搜已经保存好在绿色区域1离节点2的最远、次远距离。

          绿色区域2、 节点2的父亲节点1+父亲节点1的子树部分,这个在第一次深搜已经保存好在绿色区域2离节点1的最远、次远距离。

       那么只需要做个比较即可更新。

情况1 。  节点max_id[1] = 2,1的最远距离来自2 。 那么区域2中离节点2的最远距离second_lenth[1]。

             即  max_lenth[2] = max( max_lenth[2] , second_lenth[1] + w(1,2)) 。 

情况2 。  节点max_id[1] != 2,1的最远距离不是来自2 。 那么区域2中离节点2的最远距离max_lenth[1]。

             即  max_lenth[2] = max( max_lenth[2] , max_lenth[1]+w(1,2)) 。 

注意(树形DP最值得注意的地方): 

      dfs_1  , 先递归再DP

      dfs_2 ,   先DP再递归 

 


const int Max_N = 10008 ;

struct Edge{
       int v ;
       int w ;
       Edge(){}
       Edge(int i , int j):v(i) , w(j){}
};

vector<edge> List[Max_N] ;
int N ;
int max_lenth[Max_N] , max_id[Max_N] ;
int second_lenth[Max_N] , second_id[Max_N] ;

void dfs_1(int u , int father){
     int i , w , v ;
     for(i = 0 ; i <br>
<br>


</edge>
Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Laravel入门教程:从零开始学习最流行的PHP框架Laravel入门教程:从零开始学习最流行的PHP框架Aug 13, 2023 pm 01:21 PM

Laravel入门教程:从零开始学习最流行的PHP框架引言:Laravel是当前最流行的PHP框架之一,它易于上手、功能强大且拥有活跃的开发社区。本文将带您从零开始学习Laravel框架,并提供一些实例代码,帮助您更好地理解和掌握这个强大的工具。第一步:安装Laravel在开始之前,您需要在计算机上安装Laravel框架。最简单的方法是通过Composer进

VUE3入门实例:制作一个简单的图片裁剪器VUE3入门实例:制作一个简单的图片裁剪器Jun 15, 2023 pm 08:45 PM

Vue.js是一款流行的JavaScript前端框架,目前已经推出了最新的版本——Vue3,新版Vue在性能、体积以及开发体验上均有所提升,受到越来越多的开发者欢迎。本文将介绍如何使用Vue3制作一个简单的图片裁剪器。首先,我们需要创建一个Vue项目并安装所需的插件。可以使用VueCLI来创建项目,也可以手动搭建。这里我们以使用VueCLI的方式为例:#

从入门到精通:掌握go-zero框架从入门到精通:掌握go-zero框架Jun 23, 2023 am 11:37 AM

Go-zero是一款优秀的Go语言框架,它提供了一整套解决方案,包括RPC、缓存、定时任务等功能。事实上,使用go-zero建立一个高性能的服务非常简单,甚至可以在数小时内从入门到精通。本文旨在介绍使用go-zero框架构建高性能服务的过程,并帮助读者快速掌握该框架的核心概念。一、安装和配置在开始使用go-zero之前,我们需要安装它并配置一些必要的环境。1

快速入门:使用Go语言函数实现简单的数据可视化功能快速入门:使用Go语言函数实现简单的数据可视化功能Aug 02, 2023 pm 04:25 PM

快速入门:使用Go语言函数实现简单的数据可视化功能随着数据的快速增长和复杂性的提高,数据可视化成为了数据分析和数据表达的重要手段。在数据可视化中,我们需要使用合适的工具和技术来将数据转化为易读且易理解的图表或图形。Go语言作为一种高效且易于使用的编程语言,在数据科学领域也有着广泛的应用。本文将介绍如何使用Go语言函数来实现简单的数据可视化功能。我们将使用Go

PHP中的人脸识别入门指南PHP中的人脸识别入门指南Jun 11, 2023 am 09:16 AM

随着科技的不断发展,人脸识别技术也越来越得到了广泛的应用。而在Web开发领域中,PHP是一种被广泛采用的技术,因此PHP中的人脸识别技术也备受关注。本文将介绍PHP中的人脸识别入门指南,帮助初学者快速掌握这一领域。一、什么是人脸识别技术人脸识别技术是一种基于计算机视觉技术的生物特征识别技术,其主要应用领域包括安防、金融、电商等。人脸识别技术的核心就是对人脸进

如何快速入门Beego开发框架?如何快速入门Beego开发框架?Jun 22, 2023 am 09:15 AM

Beego是一个基于Go语言的开发框架,它提供了一套完整的Web开发工具链,包括路由、模板引擎、ORM等。如果你想快速入门Beego开发框架,以下是一些简单易懂的步骤和建议。第一步:安装Beego和Bee工具安装Beego和Bee工具是开始学习Beego的第一步。你可以在Beego官网上找到详细的安装步骤,也可以使用以下命令来安装:gogetgithub

Laravel 8:快速入门指南Laravel 8:快速入门指南Jun 20, 2023 am 09:37 AM

Laravel是一个流行的PHP框架,它提供了许多工具和功能,以使开发Web应用程序变得更加轻松和快速。Laravel8已经发布,它带来了许多新的功能和改进。在本文中,我们将学习如何快速入门Laravel8。安装Laravel8要安装Laravel8,您需要满足以下要求:PHP&gt;=7.3MySQL&gt;=5.6或MariaDB&gt;=10.

PHP摄像头调用教程:快速入门指南PHP摄像头调用教程:快速入门指南Jul 29, 2023 pm 11:13 PM

PHP摄像头调用教程:快速入门指南引言:在当今的数字时代,摄像头成为了人们生活中不可或缺的设备之一。在Web开发中,如何通过PHP调用摄像头,实现视频流的显示和处理,成为了很多开发者关注的问题。本文将为大家介绍如何快速入门使用PHP来调用摄像头。一、环境准备要使用PHP调用摄像头,我们需要准备以下环境:PHP:确保已经安装了PHP,并且安装了相应的扩展库,如

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools