当前位置:网站首页>Hdu-2196 tree DP learning notes
Hdu-2196 tree DP learning notes
2022-07-07 10:23:00 【Longka Kaka】
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 n^{2} n2). But observe the data volume of the topic n ≤ 10000 n\leq 10000 n≤10000 ,O( n 2 n^{2} n2) The time complexity of cannot meet the requirements , Generally speaking, we need to consider using O( n l o g 2 n nlog_{2}n nlog2n) The algorithm of .(O( n 1.5 n^{1.5} n1.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 :
- Keep going up
- 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 ?
- about “ Keep going up ” Value , It is the value when the parent node goes up , This can be obtained by recursion layer by layer .
- 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
边栏推荐
- JMeter loop controller and CSV data file settings are used together
- 嵌入式工程师如何提高工作效率
- Advanced function learning in ES6
- Some thoughts on the testing work in the process of R & D
- @Transcation的配置,使用,原理注意事项:
- STM32 Basics - memory mapping
- Study summary of postgraduate entrance examination in October
- Es classes and objects, prototypes
- 【acwing】789. 数的范围(二分基础)
- Use the fetch statement to obtain the repetition of the last row of cursor data
猜你喜欢
Methods of adding centerlines and centerlines in SolidWorks drawings
1324:【例6.6】整数区间
Weekly recommended short videos: what are the functions of L2 that we often use in daily life?
SQLyog数据库怎么取消自动保存更改
ArcGIS operation: batch modify attribute table
一文讲解单片机、ARM、MUC、DSP、FPGA、嵌入式错综复杂的关系
Chris Lattner, père de llvm: Pourquoi reconstruire le logiciel d'infrastructure ai
Smart city construction based on GIS 3D visualization technology
P2788 数学1(math1)- 加减算式
Fiddler break point
随机推荐
Postman interface test II
Wallys/IPQ6010 (IPQ6018 FAMILY) EMBEDDED BOARD WITH ON-BOARD WIFI DUAL BAND DUAL CONCURRENT
PDF文档签名指南
Guid primary key
Postman tutorial - scripting
The story of Plato and his three disciples: how to find happiness? How to find the ideal partner?
Postman interface test IV
Some properties of leetcode139 Yang Hui triangle
Some test points about coupon test
【二开】【JeecgBoot】修改分页参数
STM32基础知识—内存映射
High number_ Chapter 1 space analytic geometry and vector algebra_ Quantity product of vectors
Vs code specifies the extension installation location
【acwing】789. 数的范围(二分基础)
求方程ax^2+bx+c=0的根(C语言)
C#记录日志方法
Sword finger offer 38 Arrangement of strings [no description written]
Deconvolution popular detailed analysis and nn Convtranspose2d important parameter interpretation
Chris LATTNER, the father of llvm: why should we rebuild AI infrastructure software
JMeter loop controller and CSV data file settings are used together