树形DP（2019.8.9训练）-白红宇

树形DP（2019.8.9训练）

阅读量：263 次

发布时间：2019-03-01

本文共 1307 字，大约阅读时间需要 4 分钟。

树形动态规划题目分类

树的重心树的重心是指一棵树中，所有子树中节点数最少的那个点。删除重心后，生成的多棵树尽可能平衡。对于一棵n个节点的无根树，找到一个点，使得树变成以该点为根的有根树时，最大子树的节点数最少。换句话说，删除这个点后生成的最大连通块（一定是树）的节点数最少。

树的直径树的直径是指树中最长的路径长度。通常的做法是通过两次广度优先搜索（BFS）找到最长路径。第一次BFS找到最远的节点u，第二次BFS从u出发找到最远的节点v，u到v的路径即为直径。

树的选择权问题每个节点有一个权值，相邻的父节点和子节点中最多只能选择一个。目标是选择一个路径，使得权值和最大。可以使用动态规划，两个状态：一个表示不取当前节点，另一个表示取当前节点。

树的权重问题每个节点有一个权值，相邻的父节点和子节点中最多只能选择一个。目标是选择权值和最大的路径。与上述问题类似，使用动态规划解决。

树的背包问题每个节点有一个权重，每个子树的总权重不超过背包容量。目标是最大化总值。递归动态规划方法。

最长链问题找到一条最长链，使得每条链中的权重递增。递归方法通过记录当前最长和次长的权重来更新。

以下是优化后的代码示例，使用scanf输入以提高效率：

#include 
   
    #include 
    
     #include 
     #include 
      
       using namespace std;const int N = 6010;int n, m, y, z, cnt, val[N], head[N], dp[N][2];struct edge { int to, next; };void add(int x, int y) {    e[cnt].to = y;    e[cnt].next = head[x];    head[x] = cnt++;}void dfs(int u, int father) {    dp[u][0] = 0;    dp[u][1] = val[u];    for (int i = head[u]; i != -1; i = e[i].next) {        int v = e[i].to;        if (v == father) continue;        dfs(v, u);        dp[u][0] += max(dp[v][0], dp[v][1]);        dp[u][1] += dp[v][0];    }}int main() {    while (scanf("%d", &n) != EOF) {        // 读取输入并初始化        // ...        // 调用DFS        dfs(s, 0);        // 输出结果        printf("%d\n", max(dp[s][0], dp[s][1]));    }    return 0;}

这些代码经过优化，使用scanf输入，适合在线评测平台。

转载地址：http://kmxx.baihongyu.com/

你可能感兴趣的文章