Hdu-2196 tree DP learning notes

HDU-2196 Tree form DP Learning notes

Tree form DP brief introduction

Tree form dp Especially on the data structure of tree DP. Because the tree itself has Substructure The nature of ( Trees and subtrees ), It is very suitable for recursion and recursion , accord with dp The nature of .

Tree form dp More commonly used in dfs Algorithm , You need to master several kinds of trees Representation And tree Traverse the way .

Title Description

For a rooted tree , For a given edge weight （ Natural number ）, Find the distance of the farthest node from each node .

Their thinking

First of all, consider The brute force algorithm How do you do it? . The method of violent algorithm is For every node , Take this node as the root node and find the distance to all leaf nodes once , And then take the maximum . Solving the maximum value of each node requires traversing the whole tree once , The single time complexity is O(n), The overall time complexity is O($n^2$). But observe the data volume of the topic $n\le 10000$ ,O($n^2$) The time complexity of cannot meet the requirements , Generally speaking, we need to consider using O($nlo{g}_{2}n$) The algorithm of .（O($n^{1.5}$) It's also possible to live , But this kind of time complexity usually appears in number theory , Instead of a tree structure ）

Violence can't pass , Then we consider whether we can use DP.

First , It's easy to think of , If the specified direction can only be from top to bottom （ From roots to leaves ）, So for a node , You can easily find the distance to the farthest node .

Method ： Starting from the leaf node , Up in turn , The longest distance value of each node is equal to ： Among all child nodes of this node , The longest distance value of the child node + The distance between it and the child node The largest value in .

that , Now we know the maximum distance corresponding to the node when it goes up , You can get the answer . How to ask ？

Go up , For the father node , There are two choices ：

1. Keep going up
2. Go to other child nodes

that , As long as we know the value in these two cases , You can know the final result . How to find these two values ？

1. about “ Keep going up ” Value , It is the value when the parent node goes up , This can be obtained by recursion layer by layer .
2. about “ Go to other child nodes ” Value , What we need to find is the maximum value of the value going to other nodes , That is, exclude the current node . In fact, there are only two situations ：A. The current node is the node on the maximum value path of the parent node B. And A contrary . If it's the case A, Then find the maximum value of other nodes , In fact, it is seeking the next largest value of the parent node . If it's the case B, In fact, it is to find the maximum value of the current node going down .

In this way , These two values are obtained .

So definition ：

dp[i][0]:i The maximum downward value of node number 
dp[i][1]:i The next largest value down from node No 
dp[i][2]:i The maximum value of node No. upward 

You can write the situation of going up State shift Code ：

if(cost+dp[cur][0]==dp[father][0])// Is the subtree corresponding to the maximum value below the parent node 
    dp[cur][2]=max(dp[father][2],dp[father][1])+cost;
else
    dp[cur][2]=max(dp[father][2],dp[father][0])+cost;

The next part is simple , For each child node , Just update the maximum and sub maximum values ：

if(dp[j][0]+cost>dp[cur][0])// Greater than the maximum value of the current node  
{
    
    dp[cur][1]=dp[cur][0];
    dp[cur][0]=dp[j][0]+cost;
}else if(dp[j][0]+cost>dp[cur][1])// Greater than the next largest value of the current node  
{
    
    dp[cur][1]=dp[j][0]+cost;
}

AC Code

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<cstring>
#define endl '\n'
using namespace std;
const int MAX_N=1e4+10;
int dp[MAX_N][3];
vector<pair<int,int> > g[MAX_N];
int n;
void dfs1(int cur)
{
    
	if(g[cur].size()==0)
	{
    
		dp[cur][0]=0;
		dp[cur][1]=0;
		return ;
	}
	for(int i=0;i<g[cur].size();i++)
	{
    
		int j=g[cur][i].first,cost=g[cur][i].second;
		dfs1(j);
		if(dp[j][0]+cost>dp[cur][0])// Greater than the maximum value of the current node  
		{
    
			dp[cur][1]=dp[cur][0];
			dp[cur][0]=dp[j][0]+cost;
		}else if(dp[j][0]+cost>dp[cur][1])// Greater than the next largest value of the current node  
		{
    
			dp[cur][1]=dp[j][0]+cost;
		}
	}
}
void dfs2(int cur,int father=-1,int cost=0)
{
    
	if(cur==0)dp[cur][2]=0;
	else// State shift  
	{
    
		if(cost+dp[cur][0]==dp[father][0])// Is the subtree corresponding to the maximum value below the parent node  
			dp[cur][2]=max(dp[father][2],dp[father][1])+cost;
		else
			dp[cur][2]=max(dp[father][2],dp[father][0])+cost;
	}
	for(int i=0;i<g[cur].size();i++)
		dfs2(g[cur][i].first,cur,g[cur][i].second);
}
int main()
{
    
	while(cin>>n)
	{
    
		for(int i=0;i<n;i++)
			g[i].clear();
		memset(dp,0,sizeof(dp));
		int father,cost;
		for(int i=1;i<n;i++)
		{
    
			cin>>father>>cost;
			father--;
			g[father].push_back(make_pair(i,cost));
		}
		dfs1(0);
		dfs2(0);
		for(int i=0;i<n;i++)
		{
    
			cout<<max(dp[i][0],dp[i][2])<<endl;
		}
	}
	return 0;
}

Learning books ： Algorithm competition from entry to advanced