当前位置:网站首页>HDU-2196 树形DP学习笔记
HDU-2196 树形DP学习笔记
2022-07-07 08:10:00 【龙卡卡卡】
HDU-2196 树形DP学习笔记
树形DP简介
树形dp特指在树这种数据结构上进行的DP。由于树本身具有子结构的性质(树和子树),很适合用来做递归和递推,符合dp的性质。
树形dp中用的比较多的是dfs算法,需要熟练掌握树的几种表示方法和树的遍历方式。
题目描述
对于一棵有根树,对于给定的边权值(自然数),求距离每一个结点最远的结点的距离。
解题思路
首先考虑一下暴力算法怎么做。暴力算法的做法即 对于每于一个结点,将该结点作为根结点求一次到所有叶子结点的距离,然后取最大值。求解每个结点的最大值都要遍历一次整棵树,单次时间复杂度为O(n),整体时间复杂度为O( n 2 n^{2} n2)。但是观察题目数据量 n ≤ 10000 n\leq 10000 n≤10000 ,O( n 2 n^{2} n2)的时间复杂度无法满足要求,一般来说需要考虑使用O( n l o g 2 n nlog_{2}n nlog2n)的算法。(O( n 1.5 n^{1.5} n1.5)也是可以过的,但是这种时间复杂度一般出现在数论中,而不是树形结构)
暴力过不了了,然后我们考虑能否使用DP。
首先,容易想到的是,如果规定走的方向只能从上往下(从树根到树叶),那么对于一个结点而言,可以轻松的求到他到达最远结点的距离。
方法:从叶子结点开始,依次往上,每个结点的最远距离值就等于:该结点的所有子结点中, 子结点的最远距离值+它与该子结点的距离 中最大的那一个值。
那么,现在再知道结点在往上走的情况下对应的距离最大值,就可以得出答案了。如何求呢?
往上走的情况下,对于走到的父亲结点,有两个选择:
- 继续往上走
- 往其他子结点走
那么,只要知道了这两种情况下的值,就可以知道最终结果了。这两个值又如何求呢?
- 对于“继续往上走”的值,就是父节点往上走情况下的值,这个可以通过递推一层一层的得到。
- 对于“往其他子结点走”的值,我们需要求得的是往其他结点走的值的最大值,即排除当前结点。那么其实无非是两种情况:A.当前结点是父节点往下走的最大值路径上的结点 B.与A相反。如果是情况A,那么求其他结点的最大值,其实就是在求父节点往下走的次大值。如果是情况B,那么其实就是求当前结点往下走的最大值。
如此一来,这两个值就都求到了。
那么定义:
dp[i][0]:i号结点向下的最大值
dp[i][1]:i号结点向下的次大值
dp[i][2]:i号结点向上的最大值
可以写出往上走的情况的状态转移代码:
if(cost+dp[cur][0]==dp[father][0])//是父节点往下的最大值对应的子树
dp[cur][2]=max(dp[father][2],dp[father][1])+cost;
else
dp[cur][2]=max(dp[father][2],dp[father][0])+cost;
往下走的部分很简单,就是对于每一个子结点,更新一下最大值和次大值就行了:
if(dp[j][0]+cost>dp[cur][0])//大于当前结点的最大值
{
dp[cur][1]=dp[cur][0];
dp[cur][0]=dp[j][0]+cost;
}else if(dp[j][0]+cost>dp[cur][1])//大于当前结点的次大值
{
dp[cur][1]=dp[j][0]+cost;
}
AC代码
#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])//大于当前结点的最大值
{
dp[cur][1]=dp[cur][0];
dp[cur][0]=dp[j][0]+cost;
}else if(dp[j][0]+cost>dp[cur][1])//大于当前结点的次大值
{
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//状态转移
{
if(cost+dp[cur][0]==dp[father][0])//是父节点往下的最大值对应的子树
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;
}
学习书籍:算法竞赛从入门到进阶
边栏推荐
- Memory ==c language 1
- Encrypt and decrypt stored procedures (SQL 2008/sql 2012)
- ORM模型--数据记录的创建操作,查询操作
- Advanced function learning in ES6
- 电表远程抄表拉合闸操作命令指令
- Parameter sniffing (2/2)
- When there are pointer variable members in the custom type, the return value and parameters of the assignment operator overload must be reference types
- LLVM之父Chris Lattner:為什麼我們要重建AI基礎設施軟件
- 根据设备信息进行页面跳转至移动端页面或者PC端页面
- HAL库配置通用定时器TIM触发ADC采样,然后DMA搬运到内存空间。
猜你喜欢
随机推荐
Methods of adding centerlines and centerlines in SolidWorks drawings
Memory ==c language 1
高数_第1章空间解析几何与向量代数_向量的数量积
ORM -- database addition, deletion, modification and query operation logic
The landing practice of ByteDance kitex in SEMA e-commerce scene
SolidWorks工程图中添加中心线和中心符号线的办法
Can I open a stock trading account online? Is it safe
Official media attention! The list of top 100 domestic digital collection platforms was released, and the industry accelerated the healthy development of compliance
Postman interface test I
ISP、IAP、ICP、JTAG、SWD的编程特点
Postman tutorial - scripting
嵌入式背景知识-芯片
MCU与MPU的区别
Prototype object in ES6
Study summary of postgraduate entrance examination in September
电表远程抄表拉合闸操作命令指令
【acwing】786. 第k个数
Factorial implementation of large integer classes
Appx代碼簽名指南
Postman interface test VII