Heim Datenbank MySQL-Tutorial 树形DP图画入门题解2 (HDU2196)

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

Jun 07, 2016 pm 03:49 PM
http 入门

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>
Nach dem Login kopieren
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße Artikel -Tags

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Ein Diffusionsmodell-Tutorial, das Ihre Zeit wert ist, von der Purdue University Ein Diffusionsmodell-Tutorial, das Ihre Zeit wert ist, von der Purdue University Apr 07, 2024 am 09:01 AM

Ein Diffusionsmodell-Tutorial, das Ihre Zeit wert ist, von der Purdue University

Generieren Sie PPT mit einem Klick! Kimi: Lassen Sie zuerst die „PPT-Wanderarbeiter' populär werden Generieren Sie PPT mit einem Klick! Kimi: Lassen Sie zuerst die „PPT-Wanderarbeiter' populär werden Aug 01, 2024 pm 03:28 PM

Generieren Sie PPT mit einem Klick! Kimi: Lassen Sie zuerst die „PPT-Wanderarbeiter' populär werden

Alle CVPR 2024-Auszeichnungen bekannt gegeben! Fast 10.000 Menschen nahmen offline an der Konferenz teil und ein chinesischer Forscher von Google gewann den Preis für den besten Beitrag Alle CVPR 2024-Auszeichnungen bekannt gegeben! Fast 10.000 Menschen nahmen offline an der Konferenz teil und ein chinesischer Forscher von Google gewann den Preis für den besten Beitrag Jun 20, 2024 pm 05:43 PM

Alle CVPR 2024-Auszeichnungen bekannt gegeben! Fast 10.000 Menschen nahmen offline an der Konferenz teil und ein chinesischer Forscher von Google gewann den Preis für den besten Beitrag

Eine Pflichtlektüre für technische Anfänger: Analyse der Schwierigkeitsgrade von C-Sprache und Python Eine Pflichtlektüre für technische Anfänger: Analyse der Schwierigkeitsgrade von C-Sprache und Python Mar 22, 2024 am 10:21 AM

Eine Pflichtlektüre für technische Anfänger: Analyse der Schwierigkeitsgrade von C-Sprache und Python

Von Bare-Metal bis hin zu einem großen Modell mit 70 Milliarden Parametern finden Sie hier ein Tutorial und gebrauchsfertige Skripte Von Bare-Metal bis hin zu einem großen Modell mit 70 Milliarden Parametern finden Sie hier ein Tutorial und gebrauchsfertige Skripte Jul 24, 2024 pm 08:13 PM

Von Bare-Metal bis hin zu einem großen Modell mit 70 Milliarden Parametern finden Sie hier ein Tutorial und gebrauchsfertige Skripte

KI im Einsatz |. AI hat einen Lebens-Vlog eines allein lebenden Mädchens erstellt, der innerhalb von drei Tagen Zehntausende Likes erhielt KI im Einsatz |. AI hat einen Lebens-Vlog eines allein lebenden Mädchens erstellt, der innerhalb von drei Tagen Zehntausende Likes erhielt Aug 07, 2024 pm 10:53 PM

KI im Einsatz |. AI hat einen Lebens-Vlog eines allein lebenden Mädchens erstellt, der innerhalb von drei Tagen Zehntausende Likes erhielt

Der leitende NVIDIA-Architekt zählt die 12 Schwachstellen von RAG auf und vermittelt Lösungen Der leitende NVIDIA-Architekt zählt die 12 Schwachstellen von RAG auf und vermittelt Lösungen Jul 11, 2024 pm 01:53 PM

Der leitende NVIDIA-Architekt zählt die 12 Schwachstellen von RAG auf und vermittelt Lösungen

VSCode-Erste-Schritte-Leitfaden: Ein Muss für Anfänger, um die Verwendungsfähigkeiten schnell zu erlernen! VSCode-Erste-Schritte-Leitfaden: Ein Muss für Anfänger, um die Verwendungsfähigkeiten schnell zu erlernen! Mar 26, 2024 am 08:21 AM

VSCode-Erste-Schritte-Leitfaden: Ein Muss für Anfänger, um die Verwendungsfähigkeiten schnell zu erlernen!

See all articles