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 KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

Video Face Swap

Video Face Swap

Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heiße Werkzeuge

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

Diffusion kann nicht nur besser imitieren, sondern auch „erschaffen“. Das Diffusionsmodell (DiffusionModel) ist ein Bilderzeugungsmodell. Im Vergleich zu bekannten Algorithmen wie GAN und VAE im Bereich der KI verfolgt das Diffusionsmodell einen anderen Ansatz. Seine Hauptidee besteht darin, dem Bild zunächst Rauschen hinzuzufügen und es dann schrittweise zu entrauschen. Das Entrauschen und Wiederherstellen des Originalbilds ist der Kernbestandteil des Algorithmus. Der endgültige Algorithmus ist in der Lage, aus einem zufälligen verrauschten Bild ein Bild zu erzeugen. In den letzten Jahren hat das phänomenale Wachstum der generativen KI viele spannende Anwendungen in der Text-zu-Bild-Generierung, Videogenerierung und mehr ermöglicht. Das Grundprinzip dieser generativen Werkzeuge ist das Konzept der Diffusion, ein spezieller Sampling-Mechanismus, der die Einschränkungen bisheriger Methoden überwindet.

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

Kimi: In nur einem Satz, in nur zehn Sekunden ist ein PPT fertig. PPT ist so nervig! Um ein Meeting abzuhalten, benötigen Sie einen PPT; um einen wöchentlichen Bericht zu schreiben, müssen Sie einen PPT vorlegen, auch wenn Sie jemanden des Betrugs beschuldigen PPT. Das College ähnelt eher dem Studium eines PPT-Hauptfachs. Man schaut sich PPT im Unterricht an und macht PPT nach dem Unterricht. Als Dennis Austin vor 37 Jahren PPT erfand, hatte er vielleicht nicht damit gerechnet, dass PPT eines Tages so weit verbreitet sein würde. Wenn wir über unsere harte Erfahrung bei der Erstellung von PPT sprechen, treiben uns Tränen in die Augen. „Es dauerte drei Monate, ein PPT mit mehr als 20 Seiten zu erstellen, und ich habe es Dutzende Male überarbeitet. Als ich das PPT sah, musste ich mich übergeben.“ war PPT.“ Wenn Sie ein spontanes Meeting haben, sollten Sie es tun

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

Am frühen Morgen des 20. Juni (Pekinger Zeit) gab CVPR2024, die wichtigste internationale Computer-Vision-Konferenz in Seattle, offiziell die besten Beiträge und andere Auszeichnungen bekannt. In diesem Jahr wurden insgesamt 10 Arbeiten ausgezeichnet, darunter zwei beste Arbeiten und zwei beste studentische Arbeiten. Darüber hinaus gab es zwei Nominierungen für die beste Arbeit und vier Nominierungen für die beste studentische Arbeit. Die Top-Konferenz im Bereich Computer Vision (CV) ist die CVPR, die jedes Jahr zahlreiche Forschungseinrichtungen und Universitäten anzieht. Laut Statistik wurden in diesem Jahr insgesamt 11.532 Arbeiten eingereicht, von denen 2.719 angenommen wurden, was einer Annahmequote von 23,6 % entspricht. Laut der statistischen Analyse der CVPR2024-Daten des Georgia Institute of Technology befassen sich die meisten Arbeiten aus Sicht der Forschungsthemen mit der Bild- und Videosynthese und -generierung (Imageandvideosyn

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

Wir wissen, dass LLM auf großen Computerclustern unter Verwendung umfangreicher Daten trainiert wird. Auf dieser Website wurden viele Methoden und Technologien vorgestellt, die den LLM-Trainingsprozess unterstützen und verbessern. Was wir heute teilen möchten, ist ein Artikel, der tief in die zugrunde liegende Technologie eintaucht und vorstellt, wie man einen Haufen „Bare-Metals“ ohne Betriebssystem in einen Computercluster für das LLM-Training verwandelt. Dieser Artikel stammt von Imbue, einem KI-Startup, das allgemeine Intelligenz durch das Verständnis der Denkweise von Maschinen erreichen möchte. Natürlich ist es kein einfacher Prozess, einen Haufen „Bare Metal“ ohne Betriebssystem in einen Computercluster für das Training von LLM zu verwandeln, aber Imbue hat schließlich erfolgreich ein LLM mit 70 Milliarden Parametern trainiert der Prozess akkumuliert

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

Herausgeber des Machine Power Report: Yang Wen Die Welle der künstlichen Intelligenz, repräsentiert durch große Modelle und AIGC, hat unsere Lebens- und Arbeitsweise still und leise verändert, aber die meisten Menschen wissen immer noch nicht, wie sie sie nutzen sollen. Aus diesem Grund haben wir die Kolumne „KI im Einsatz“ ins Leben gerufen, um detailliert vorzustellen, wie KI durch intuitive, interessante und prägnante Anwendungsfälle für künstliche Intelligenz genutzt werden kann, und um das Denken aller anzuregen. Wir heißen Leser auch willkommen, innovative, praktische Anwendungsfälle einzureichen. Videolink: https://mp.weixin.qq.com/s/2hX_i7li3RqdE4u016yGhQ Vor kurzem wurde der Lebens-Vlog eines allein lebenden Mädchens auf Xiaohongshu populär. Eine Animation im Illustrationsstil, gepaart mit ein paar heilenden Worten, kann in nur wenigen Tagen leicht erlernt werden.

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

Titel: Ein Muss für technische Anfänger: Schwierigkeitsanalyse der C-Sprache und Python, die spezifische Codebeispiele erfordert. Im heutigen digitalen Zeitalter ist Programmiertechnologie zu einer immer wichtigeren Fähigkeit geworden. Ob Sie in Bereichen wie Softwareentwicklung, Datenanalyse, künstliche Intelligenz arbeiten oder einfach nur aus Interesse Programmieren lernen möchten, die Wahl einer geeigneten Programmiersprache ist der erste Schritt. Unter vielen Programmiersprachen sind C-Sprache und Python zwei weit verbreitete Programmiersprachen, jede mit ihren eigenen Merkmalen. In diesem Artikel werden die Schwierigkeitsgrade der C-Sprache und von Python analysiert

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

Retrieval-Augmented Generation (RAG) ist eine Technik, die Retrieval nutzt, um Sprachmodelle zu verbessern. Bevor ein Sprachmodell eine Antwort generiert, ruft es insbesondere relevante Informationen aus einer umfangreichen Dokumentendatenbank ab und verwendet diese Informationen dann zur Steuerung des Generierungsprozesses. Diese Technologie kann die Genauigkeit und Relevanz von Inhalten erheblich verbessern, das Problem der Halluzinationen wirksam lindern, die Geschwindigkeit der Wissensaktualisierung erhöhen und die Nachverfolgbarkeit der Inhaltsgenerierung verbessern. RAG ist zweifellos einer der spannendsten Bereiche der Forschung im Bereich der künstlichen Intelligenz. Weitere Informationen zu RAG finden Sie im Kolumnenartikel auf dieser Website „Was sind die neuen Entwicklungen bei RAG, das sich darauf spezialisiert hat, die Mängel großer Modelle auszugleichen?“ Diese Rezension erklärt es deutlich. Aber RAG ist nicht perfekt und Benutzer stoßen bei der Verwendung oft auf einige „Problempunkte“. Kürzlich die fortschrittliche generative KI-Lösung von NVIDIA

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 (Visual Studio Code) ist ein von Microsoft entwickelter Open-Source-Code-Editor. Er verfügt über leistungsstarke Funktionen und umfangreiche Plug-in-Unterstützung, was ihn zu einem der bevorzugten Tools für Entwickler macht. Dieser Artikel bietet eine Einführung für Anfänger, die ihnen hilft, schnell die Fähigkeiten im Umgang mit VSCode zu erlernen. In diesem Artikel stellen wir die Installation von VSCode, grundlegende Bearbeitungsvorgänge, Tastenkombinationen, Plug-In-Installation usw. vor und stellen den Lesern spezifische Codebeispiele zur Verfügung. 1. Installieren Sie zuerst VSCode, wir brauchen

See all articles