HDU 2196 Computer(树形dp)

H D U 2196 C o m p u t e r (树形 d p ) \Huge{HDU 2196 Computer(树形dp)} HDU2196Computer(树形dp

文章目录


题目链接:Problem - 2196 (hdu.edu.cn)

题意

给出一个n个节点的无根树,求每个节点所能到达的最远距离。

img

思路

  • 本题解思路为树形dp思路。
  • 注意题目的输入要求。
  • 题目为多实例!

跟据二叉树的定义,每个节点至多有一个父节点(只有根节点没有),我们会发现每个节点能够到达的最远距离只有下图两种情况。

在这里插入图片描述

那么我们可以先通过一次dfs,从叶节点向上返回;记录每个节点的子节点中的最大路径长度次大路径长度,因为会出现图片中①的情况。

然后再通过一次dfs,从根节点向下遍历;找出每个节点的最大反向路径长度,对应的是图片中的②情况。

对于最大路径长度次大路径长度最大反向路径长度,我们可以用 d p [ i ] [ j ] , j ∈ ( 0 , 1 , 2 ) dp[i][j],j\in(0,1,2) dp[i][j],j(0,1,2)来记录每个节点的状态。

在第二次dfs的过程中,我们可以对每个节点的子节点进行状态转移,状态转移方程为:
{ d p [ 2 ] [ s o n ] = m a x ( d p [ 2 ] [ f a t h e r ] , d p [ 1 ] [ f a t h e r ] + w e i g h t )     s o n 为 f a t h e r 子节点中的最大路径 d p [ 2 ] [ s o n ] = m a x ( d p [ 2 ] [ f a t h e r ] , d p [ 0 ] [ f a t h e r ] + w e i g h t )     s o n 不为 f a t h e r 子节点中的最大路径 \begin{cases} & \text dp[2][son] = max(dp[2][father], dp[1][father]+weight) ~~~ son为father子节点中的最大路径\\ & \text dp[2][son] = max(dp[2][father], dp[0][father]+weight) ~~~ son不为father子节点中的最大路径 \end{cases} {dp[2][son]=max(dp[2][father],dp[1][father]+weight)   sonfather子节点中的最大路径dp[2][son]=max(dp[2][father],dp[0][father]+weight)   son不为father子节点中的最大路径
其中 0 , 1 , 2 0,1,2 0,1,2分别对应的是最大路径长度次大路径长度最大反向路径长度

最后每个节点能够到达的最远距离即为: m a x ( d p [ 0 ] [ i ] , d p [ 2 ] [ i ] ) max(dp[0][i], dp[2][i]) max(dp[0][i],dp[2][i])

标程

const int N = 10000 + 10; 

struct Edge {int to, weight;};  // 边
vector<vector<Edge>> tree;      //用于存储树的结构
int n, dp[3][N], id[N];

void dfs1(int x, int y) {
    for(auto i : tree[x]) {//正向最大距离
        if(i.to == y) continue;
        dfs1(i.to, x);
        if(dp[0][x] < dp[0][i.to] + i.weight) {
            dp[0][x] = dp[0][i.to] + i.weight;
            id[x] = i.to;
        }
    }
    for(auto i : tree[x]) {//正向次大距离
        if(i.to == y) continue;
        if(id[x] == i.to) continue;
        dp[1][x] = max(dp[1][x], dp[0][i.to] + i.weight);
    }
}

void dfs2(int x, int y) {
    for(auto i : tree[x]) {//反向最大距离
        if(i.to == y) continue;
        if(i.to == id[x])
            dp[2][i.to] = max(dp[2][x], dp[1][x]) + i.weight;
        else
            dp[2][i.to] = max(dp[2][x], dp[0][x]) + i.weight;
        dfs2(i.to, x);
    }
}

void init() {
    tree.clear(); tree.resize(n + 1);
    memset(dp, 0, sizeof dp);
    memset(id, 0, sizeof id);
}

void Solved() { 
    while(cin >> n) {
        init();
        for(int i = 2; i <= n; i ++ ) {
            int x, y; cin >> x >> y;
            tree[x].push_back({i, y});
            tree[i].push_back({x, y});
        }
        dfs1(1, -1); dfs2(1, -1);

        for(int i = 1; i <= n; i ++ ) {
            cout << max(dp[0][i], dp[2][i]) << endl;
        }
    }
}

相关推荐

  1. 信号塔(树形dp

    2024-05-25 20:39:05       33 阅读
  2. 数字转换(树形DP

    2024-05-25 20:39:05       24 阅读
  3. 动态规划-树形DP入门-自上而下树形DP

    2024-05-25 20:39:05       59 阅读
  4. C. Infected Tree -树形dp

    2024-05-25 20:39:05       65 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-05-25 20:39:05       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-05-25 20:39:05       100 阅读
  3. 在Django里面运行非项目文件

    2024-05-25 20:39:05       82 阅读
  4. Python语言-面向对象

    2024-05-25 20:39:05       91 阅读

热门阅读

  1. 最小生成树

    2024-05-25 20:39:05       36 阅读
  2. Mac软件公正方式

    2024-05-25 20:39:05       31 阅读
  3. 探索 CSS、Sass 和 SCSS:区别与应用

    2024-05-25 20:39:05       35 阅读
  4. Rom应用开发遇到得一些小bug

    2024-05-25 20:39:05       32 阅读
  5. Go语言垃圾回收机制原理

    2024-05-25 20:39:05       25 阅读
  6. C++实现童年游戏

    2024-05-25 20:39:05       31 阅读
  7. Web3 知识体系架构图

    2024-05-25 20:39:05       35 阅读
  8. Django 里的app概念

    2024-05-25 20:39:05       33 阅读