树形DP(邻接表)

前言

本篇的代码均是由邻接表来进行存储，大概在还会再来一个用链式前向星版的吧~ （下次一定）

ps: 笔者已经很用心的在打$LaTeX$了，但还是不够规范，望路过的大巨佬们多多指正

概念

度娘说

树形动态规划问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。

感觉好像并不明白她在说什么 其实笔者个人理解，树形DP更像是记忆化搜索，各个节点都像树一样连接着。（无环图）树形DP顾名思义就是像树一样的DP，在有n个节点的时候，有n-1条边连接着。 such as this 在解决树形DP的问题时，我们通常以节点从深至浅作为阶段，同时以递归来实现。就像后序遍历一样。

那么树形DP有什么作用呢？下面引出三种最版的题（也是今天笔者将要在本篇中写的）。

最大独立子集树的重心树的直径

最大独立子集

什么是最大独立子集呢？让我们来引出一道题来看看。

没有上司的晚会

题目描述

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参加宴会。

输入格式

第一行一个整数N。(1≤N≤6000)

接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128≤Ri≤127)

接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

最后一行输入0,0。

输出格式

第1行：输出最大的快乐指数。

样例

样例输入 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 样例输出 5

从上题中我们就可以看见，对于每个节点，如果选中了它，就不可能选它的父亲节点和儿子节点。那么对于每一个节点我们就有了两种状态，选与不选。 设第i个为$dp[i]$， $dp[i][1]$表示选它自己$dp[i][0]$表示不选它自己 那么状态转移方程就显而易见了

$dp[i][0]=\sum ma{x}_{(}dp[j][0],dp[j][1])———j\in son(i)$ $dp[i][1]=\sum dp[j][0]———j\in son(i)$

#include <cstdio> #include <algorithm> #include <vector> using namespace std; const int maxn = 6005; int n; int h[maxn]; int flag[maxn]; vector<int> a[maxn]; int dp[maxn][2]; void tree_dp(int x){ dp[x][1] = h[x]; dp[x][0] = 0; for(int i = 0; i < a[x].size(); i ++){ int y = a[x][i]; tree_dp(y); dp[x][0] += max(dp[y][1], dp[y][0]); dp[x][1] += dp[y][0]; } } int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++){ scanf("%d", &h[i]); } for(int i = 1; i < n; i ++){ int x, y; scanf("%d %d", &x, &y); flag[x] = 1; a[y].push_back(x); } int root; for(int i = 1; i <= n; i ++){ if(!flag[i]){ root = i; break; } } tree_dp(root); printf("%d", max(dp[root][0], dp[root][1])); return 0; }

树的重心

重心是指地球对物体中每一微小部分引力的合力作用点。物体的每一微小部分都受地心引力作用(见万有引力)，这些引力可近似地看成为相交于地心的汇交力系。由于物体的尺寸远小于地球半径，所以可近似地把作用在一般物体上的引力视为平行力系，物体的总重量就是这些引力的合力 。

不好意思这是物理

数学上的重心是指三角形的三条中线的交点，其证明定理有燕尾定理或塞瓦定理，应用定理有梅涅劳斯定理、塞瓦定理。

这才对嘛（以上两条皆来自于百度百科） 在树中的重心是指，去掉该点后，独立子树的节点个数最大的最小

以题举例

求树的重心

题目描述

树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点1后，树将分成两个连通块：（2,4,5），（3,6,7），则最大的连通块包含节点个数为3。若去掉点2，则树将分成3个部分，（4），（5），（1,3,6,7）最大的连通块包含4个节点；第一种方法可以得到更小的最大联通分量。可以发现，其他方案不可能得到比3更小的值了。所以，点1是树的重心。

输入格式

输入：第一行一个整数n，表示树的结点个数。（n<100）

接下来n-1行，每行两个数i，j。表示i和j有边相连。

输出格式

输出：第一行一个整数k，表示重心的个数。

接下来K行，每行一个整数，表示重心。按从小到大的顺序给出。

样例

样例输入 7 1 2 1 3 2 4 2 5 3 6 3 7 样例输出 1 1

其实解决这个问题，我们只需要知道与每个点的子树的节点数，通过"删除重心后所得的所有子树，节点数不超过原树的 $\frac{1}{2}$，一棵树最多有两个重心，且相邻。"这一性质来找到重心。 （上面的这一性质其实很好证明（并不严谨，只是为了方便理解），因为我们除了链的根与叶子以外都有至少两个度，如果删除重心后所得的所有子树，节点数超过原树的 $\frac{1}{2}$， 那么为什么不能选取该子树的节点为重心呢， 如果原有奇数个点，找到最中间的即可，原有偶数个节点，取其节点数/2的向上，向下取整都可以为为重心）

#include <cstdio> #include <algorithm> #include <vector> using namespace std; const int maxn = 105; int Max(int x, int y){ return x > y ? x : y; } int Min(int x, int y){ return x < y ? x : y; } struct node{ int x, f; }; int n; vector<int> a[maxn]; int siz[maxn], vis[maxn]; int nimsum = 0x3f3f3f3f; int ans[maxn]; int cnt; void dfs(int x, int f){ bool flag; flag = 1; siz[x] = 1; for(int i = 0; i < a[x].size(); i ++){ int y = a[x][i]; if(!vis[y]){ vis[y] = 1; dfs(y, x); siz[x] += siz[y]; if(siz[y] > n / 2){ flag = 0; } } } if(n - siz[x] > n / 2){ flag = 0; } if(flag){ cnt ++; ans[cnt] = x; } } int main() { scanf("%d", &n); for(int i = 1; i < n; i ++){ int x, y; scanf("%d %d", &x, &y); a[x].push_back(y); a[y].push_back(x); } vis[1] = 1; dfs(1, -1); sort(ans + 1, ans + cnt + 1); printf("%d\n", cnt); for(int i = 1; i <= cnt; i ++){ printf("%d\n", ans[i]); } return 0; }

笔者在做这道题时，将flag定义在了全局，以至于只能输出0。 因为在子节点不为重心时，flag会为0，但回溯之后flag还是0，但其父节点却有可能是重心，这样就会找不到重心，以至于只能输出0（如下图）

树的直径

题目描述

给定一个有个节点的树，树以个点条边的无向图形式给出， 求树的直径。

输入格式

输入的第1行为包含了一个正整数，为这棵二叉树的结点数。

接下来N行，每行有个正整数，表示有一条从到的无向边。

输出格式

输出包括1个正整数，为这棵二叉树的直径。

样例

样例输入 10 1 2 1 3 2 4 4 5 4 6 1 7 5 8 7 9 7 10 样例输出 6

直径我们都知道是啥，那什么是树的直径呢？就是树上两点距离的最大值(做题思路在代码下)

#include <cstdio> #include <algorithm> #include <vector> #include <cstring> using namespace std; const int maxn = 1e6 + 5; int n; vector<int> a[maxn]; int ans[maxn]; int d[maxn]; bool vis[maxn]; void dfs(int x){ vis[x] = 1; for(int i = 0; i < a[x].size(); i ++){ int y = a[x][i]; if(!vis[y]){ dfs(y); ans[x] = max(ans[x], d[x] + d[y] + 1); d[x] = max(d[x], d[y] + 1); } } } int main() { scanf("%d", &n); for(int i = 1; i < n; i ++){ int x, y; scanf("%d %d", &x, &y); a[x].push_back(y); a[y].push_back(x); } int an = 0; dfs(1); for(int i = 1; i <= n; i ++){ an = max(an, ans[i]); } printf("%d", an); return 0; }

$d[x]$表示目前遍历到的距离x最远的链，$ans[x]$表示经过x点目前最长的链

那么

ans[x] = max(ans[x], d[x] + d[y] + 1)

是什么意思呢？ 让我们联系一下

$ans[x]$表示经过x点目前最长的链

因为$d[x]$表示目前遍历到的距离x最远的链，如果$d[y]$为次长的链。则没有问题。如果$d[y]$为最长的链，要么d[x]为次长链要么在之后的$d[y]$为次长链。 所以上述做法是成立的~~

结语

笔者应该很快就会写出链式前向星版的树形DP，总之下次一定~