树形DP图画入门题解2 (HDU2196)
Jun 07, 2016 pm 03:49 PMhttp://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] ; 次远距离, 转移儿子节点
图1 : 第一次深搜, 当节点1的子树(绿色部分)遍历完回退的时候,最远次远距离只能是从(红色部分)2,6,9过来,
转移儿子节点就在2,6,9中选择。 也就是说max_id【1】 , second_id【1】 中存储的是2,6,9 中的某个。
图2 : 第一次深搜, 当节点2的子树(绿色部分)遍历完回退的时候,最远次远距离只能是从(红色部分)3,5过来,
转移儿子节点就在3,5中选择。 也就是说max_id【2】 , second_id【2】 中存储的是3,5 中的某个。
【第二次深搜】 : 求每个节点在整棵树上的最远、次远距离
图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>

Heißer Artikel

Hot-Tools-Tags

Heißer Artikel

Heiße Artikel -Tags

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

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

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

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

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!
