Home Database Mysql Tutorial 树形DP图画入门题解2 (HDU2196)

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

Jun 07, 2016 pm 03:49 PM
http getting Started

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>
Copy after login
Statement of this Website
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

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 ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

A Diffusion Model Tutorial Worth Your Time, from Purdue University A Diffusion Model Tutorial Worth Your Time, from Purdue University Apr 07, 2024 am 09:01 AM

Diffusion can not only imitate better, but also "create". The diffusion model (DiffusionModel) is an image generation model. Compared with the well-known algorithms such as GAN and VAE in the field of AI, the diffusion model takes a different approach. Its main idea is a process of first adding noise to the image and then gradually denoising it. How to denoise and restore the original image is the core part of the algorithm. The final algorithm is able to generate an image from a random noisy image. In recent years, the phenomenal growth of generative AI has enabled many exciting applications in text-to-image generation, video generation, and more. The basic principle behind these generative tools is the concept of diffusion, a special sampling mechanism that overcomes the limitations of previous methods.

Generate PPT with one click! Kimi: Let the 'PPT migrant workers' become popular first Generate PPT with one click! Kimi: Let the 'PPT migrant workers' become popular first Aug 01, 2024 pm 03:28 PM

Kimi: In just one sentence, in just ten seconds, a PPT will be ready. PPT is so annoying! To hold a meeting, you need to have a PPT; to write a weekly report, you need to have a PPT; to make an investment, you need to show a PPT; even when you accuse someone of cheating, you have to send a PPT. College is more like studying a PPT major. You watch PPT in class and do PPT after class. Perhaps, when Dennis Austin invented PPT 37 years ago, he did not expect that one day PPT would become so widespread. Talking about our hard experience of making PPT brings tears to our eyes. "It took three months to make a PPT of more than 20 pages, and I revised it dozens of times. I felt like vomiting when I saw the PPT." "At my peak, I did five PPTs a day, and even my breathing was PPT." If you have an impromptu meeting, you should do it

All CVPR 2024 awards announced! Nearly 10,000 people attended the conference offline, and a Chinese researcher from Google won the best paper award All CVPR 2024 awards announced! Nearly 10,000 people attended the conference offline, and a Chinese researcher from Google won the best paper award Jun 20, 2024 pm 05:43 PM

In the early morning of June 20th, Beijing time, CVPR2024, the top international computer vision conference held in Seattle, officially announced the best paper and other awards. This year, a total of 10 papers won awards, including 2 best papers and 2 best student papers. In addition, there were 2 best paper nominations and 4 best student paper nominations. The top conference in the field of computer vision (CV) is CVPR, which attracts a large number of research institutions and universities every year. According to statistics, a total of 11,532 papers were submitted this year, and 2,719 were accepted, with an acceptance rate of 23.6%. According to Georgia Institute of Technology’s statistical analysis of CVPR2024 data, from the perspective of research topics, the largest number of papers is image and video synthesis and generation (Imageandvideosyn

A must-read for technical beginners: Analysis of the difficulty levels of C language and Python A must-read for technical beginners: Analysis of the difficulty levels of C language and Python Mar 22, 2024 am 10:21 AM

Title: A must-read for technical beginners: Difficulty analysis of C language and Python, requiring specific code examples In today's digital age, programming technology has become an increasingly important ability. Whether you want to work in fields such as software development, data analysis, artificial intelligence, or just learn programming out of interest, choosing a suitable programming language is the first step. Among many programming languages, C language and Python are two widely used programming languages, each with its own characteristics. This article will analyze the difficulty levels of C language and Python

From bare metal to a large model with 70 billion parameters, here is a tutorial and ready-to-use scripts From bare metal to a large model with 70 billion parameters, here is a tutorial and ready-to-use scripts Jul 24, 2024 pm 08:13 PM

We know that LLM is trained on large-scale computer clusters using massive data. This site has introduced many methods and technologies used to assist and improve the LLM training process. Today, what we want to share is an article that goes deep into the underlying technology and introduces how to turn a bunch of "bare metals" without even an operating system into a computer cluster for training LLM. This article comes from Imbue, an AI startup that strives to achieve general intelligence by understanding how machines think. Of course, turning a bunch of "bare metal" without an operating system into a computer cluster for training LLM is not an easy process, full of exploration and trial and error, but Imbue finally successfully trained an LLM with 70 billion parameters. and in the process accumulate

AI in use | AI created a life vlog of a girl living alone, which received tens of thousands of likes in 3 days AI in use | AI created a life vlog of a girl living alone, which received tens of thousands of likes in 3 days Aug 07, 2024 pm 10:53 PM

Editor of the Machine Power Report: Yang Wen The wave of artificial intelligence represented by large models and AIGC has been quietly changing the way we live and work, but most people still don’t know how to use it. Therefore, we have launched the "AI in Use" column to introduce in detail how to use AI through intuitive, interesting and concise artificial intelligence use cases and stimulate everyone's thinking. We also welcome readers to submit innovative, hands-on use cases. Video link: https://mp.weixin.qq.com/s/2hX_i7li3RqdE4u016yGhQ Recently, the life vlog of a girl living alone became popular on Xiaohongshu. An illustration-style animation, coupled with a few healing words, can be easily picked up in just a few days.

Counting down the 12 pain points of RAG, NVIDIA senior architect teaches solutions Counting down the 12 pain points of RAG, NVIDIA senior architect teaches solutions Jul 11, 2024 pm 01:53 PM

Retrieval-augmented generation (RAG) is a technique that uses retrieval to boost language models. Specifically, before a language model generates an answer, it retrieves relevant information from an extensive document database and then uses this information to guide the generation process. This technology can greatly improve the accuracy and relevance of content, effectively alleviate the problem of hallucinations, increase the speed of knowledge update, and enhance the traceability of content generation. RAG is undoubtedly one of the most exciting areas of artificial intelligence research. For more details about RAG, please refer to the column article on this site "What are the new developments in RAG, which specializes in making up for the shortcomings of large models?" This review explains it clearly." But RAG is not perfect, and users often encounter some "pain points" when using it. Recently, NVIDIA’s advanced generative AI solution

VSCode Getting Started Guide: A must-read for beginners to quickly master usage skills! VSCode Getting Started Guide: A must-read for beginners to quickly master usage skills! Mar 26, 2024 am 08:21 AM

VSCode (Visual Studio Code) is an open source code editor developed by Microsoft. It has powerful functions and rich plug-in support, making it one of the preferred tools for developers. This article will provide an introductory guide for beginners to help them quickly master the skills of using VSCode. In this article, we will introduce how to install VSCode, basic editing operations, shortcut keys, plug-in installation, etc., and provide readers with specific code examples. 1. Install VSCode first, we need

See all articles