树形dp
简单来说树形 d p 就是在树上做 d p 罢了 简单来说树形dp就是在树上做dp罢了 简单来说树形dp就是在树上做dp罢了
树嘛,就要符合除了根节点外每个节点只有一个父节点 树嘛,就要符合除了根节点外每个节点只有一个父节点 树嘛,就要符合除了根节点外每个节点只有一个父节点
然后分析 d p 的时候,不再是线性的前几的什么属性那种线性术语了 然后分析dp的时候,不再是线性的前几的什么属性那种线性术语了 然后分析dp的时候,不再是线性的前几的什么属性那种线性术语了
而是以 i 为根节点的树的各种属性 而是以i为根节点的树的各种属性 而是以i为根节点的树的各种属性
状态转移也从原本的前 i − 1 到前 i 个转移 状态转移也从原本的前i-1到前i个转移 状态转移也从原本的前i−1到前i个转移
而是 u 的子树向 u 为根的树转移 而是 u的子树向u为根的树转移 而是u的子树向u为根的树转移
上几道例题具体分析
例题一
思路
AC代码
#include<bits/stdc++.h>using namespace std;const int N = 1e4 + 10;int h[N], e[N], w[N], ne[N], idx;
bool st[N];
int n;
int f[N][3]; //1:最长 0 次长
int res = -0x3f3f3f3f;void add(int a, int b, int c){e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx ++;
}void dfs(int u)
{for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];dfs(j);if(f[j][1] + w[i] >= f[u][1]){f[u][0] = f[u][1];f[u][1] = f[j][1] + w[i];}else if(f[j][1] + w[i] > f[u][0]){f[u][0] = f[j][1] + w[i];}}
}int main()
{cin >> n;memset(h, -1, sizeof(h));for(int i = 1; i <= n - 1; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c);st[b] = true;}int root = 1;while(st[root]) root ++;dfs(root);for(int i = 1; i <= n; i ++){res = max(res, f[i][0] + f[i][1]);}cout << res << endl;return 0;
}
例题2
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;int h[N], e[N<<1], w[N<<1], ne[N<<1], idx;
int n;
int down1[N], down2[N], up[N], best[N], second[N];void add(int a, int b, int c)
{e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx ++;
}void dfs_d(int u, int fa)
{for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;dfs_d(j, u);if(down1[j] + w[i] >= down1[u]){down2[u] = down1[u];second[u] = best[u];best[u] = j;down1[u] = down1[j] + w[i];}else if(down1[j] + w[i] > down2[u]){down2[u] = down1[j] + w[i];second[u] = j;}}
}void dfs_u(int u, int fa)
{for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j == fa) continue;if(j == best[u]){up[j] = max(up[u], down2[u]) + w[i];}else{up[j] = max(up[u], down1[u]) + w[i];}dfs_u(j, u);}
}int main()
{memset(h, -1, sizeof(h));cin >> n;for(int i = 1; i <= n - 1; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dfs_d(1, -1);dfs_u(1, -1);int res = 1e9;for(int i = 1; i <= n; i ++){res = min(max(down1[i], up[i]), res);}cout << res << endl;return 0;
}