树形dp

---

$简单来说树形dp就是在树上做dp罢了$
$树嘛，就要符合除了根节点外每个节点只有一个父节点$
$然后分析dp的时候，不再是线性的前几的什么属性那种线性术语了$
$而是以i为根节点的树的各种属性$
$状态转移也从原本的前i-1到前i个转移$
$而是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;
}

---