状态表示$dp[u][0/1]$
集合：对于以u节点为根的子树，选择（1）或不选择（0）u节点的方案。
属性：$max$
状态计算
$dp[u][0]=sum(max(dp[k][0],dp[k][1]))$k为u所有子节点
$dp[u][1]=sum(dp[k][0])$

#include <iostream>
#include <cstring>
using namespace std;
const int N = 6010;
int happy[N];
int h[N], e[N], ne[N];
bool has_fa[N];
int dp[N][2];
int n, tot = 1;
void add(int a, int b)
{e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
void dfs(int u)
{dp[u][1] = happy[u];for (int i = h[u]; ~i; i = ne[i]){int j = e[i];dfs(j);dp[u][0] += max(dp[j][0], dp[j][1]);dp[u][1] += dp[j][0];}return ;
}
int main()
{cin >> n;for (int i = 1; i <= n; i ++ )cin >> happy[i];memset(h, -1, sizeof h);for (int i = 1; i < n; i ++ ){int a, b;cin>> a >> b;has_fa[a] = 1;add (b, a);}int root;for (int i = 1; i <= n; i ++ )if (has_fa[i] == 0) root = i;dfs(root);cout << max(dp[root][0], dp[root][1]);return 0;
}

状态表示$dp[u][i][j]$
集合：对于以u节点为根的子树，考虑到u的第i个子树并且总树枝数量为j的所有集合。
属性：$max$
状态计算
$dp[u][i][j]=max(dp[u][i-1][j-k-1]+dp[so{n}_i][cnt(so{n}_i)][k]+w_{ui})$枚举k，即分给子树i的树枝数量。

在实际书写时可以把空间压缩至二维，省掉第二个维度。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int h[N], e[N * 2], ne[N * 2], w[N * 2];
int dp[N][N];
int n, m, tot = 1;
void dfs(int u, int fa)
{for (int i = h[u]; ~i; i = ne[i]){if (e[i] == fa) continue;dfs(e[i], u);for (int j = m; j >= 0; j -- ){for (int k = 0; k < j; k ++ ){dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[e[i]][k] + w[i]);}}}return ;
}
void add(int a, int b, int c)
{e[tot] = b, w[tot] = c, ne[tot] = h[a], h[a] = tot ++ ;
}
int main()
{cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1; i < n; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dfs(1, -1);cout << dp[1][m];return 0;
}

和没有上司的舞会不同的是，本题要求一条边上至少有一个点，和前者要求一条边上最多一个点。
状态表示$dp[u][0/1]$
集合：对于以u节点为根的子树，选择（1）或不选择（0）u节点的方案。
属性：$min$
状态计算
$dp[u][0]=sum(dp[k][1]))$k为u所有子节点
$dp[u][1]=sum(min(dp[k][0],dp[k][0]))$

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1510;
int n, tot;
bool st[N];
int dp[N][2];
int h[N], e[N], ne[N];
void add(int a, int b)
{e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
void dfs(int u)
{dp[u][1] = 1;dp[u][0] = 0;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];dfs(j);dp[u][1] += min(dp[j][0], dp[j][1]);dp[u][0] += dp[j][1];}return ;
}
int main()
{while(cin >> n){tot = 0;memset(h, -1, sizeof h);memset(st, 0, sizeof st);for (int i = 1; i <= n; i ++ ){int a, cnt, b;scanf("%d:(%d)", &a, &cnt);for (int i = 1; i <= cnt; i ++ ){cin >> b;st[b] = 1;add(a, b);}}int root = 0;while(st[root]) root ++ ; dfs(root);cout << min(dp[root][0], dp[root][1]) << endl;}return 0;
}

和上一题不同的是，上一题中每个节点可以负责和它相邻的所有边，而本题中每个节点可以负责和他相邻的所有节点。
状态表示$dp[u][0/1/2]$
集合：对于以u节点为根的子树，u由子节点负责（1）或u由父节点负责（0）或u由自己负责（2）的方案。
属性：$min$
状态计算
$dp[u][0]=sum(min(dp[k][1],dp[k][2]))$
$dp[u][1]=min(dp[k][1]+sum(min(dp[s][1],d[s][2])))$k为u的一个子结点，s为除去s的所有子节点
$dp[u][2]=min(dp[k][0],dp[k][1],dp[k][2])$

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1510;
const int INF = 1e9;
int h[N], e[N], ne[N];
int n, tot;
int dp[N][3], w[N];
bool st[N];
void dfs(int u)
{dp[u][2] = w[u];for (int i = h[u]; ~i; i = ne[i]){int j = e[i];dfs(j);dp[u][2] += min(min(dp[j][0], dp[j][1]), dp[j][2]);dp[u][0] += min(dp[j][1], dp[j][2]);}dp[u][1] = INF;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];dp[u][1] = min(dp[u][1], dp[j][2] + dp[u][0] - min(dp[j][1], dp[j][2]));}return ;
}
void add(int a, int b)
{e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
int main()
{cin >> n;memset(h, -1, sizeof h);for (int i = 1; i <= n; i ++ ){int a, b, cnt;cin >> a >> w[a] >> cnt;while (cnt -- ){cin >> b;st[b] = 1;add(a, b);}}int root = 1;while(st[root]) root ++ ;dfs(root);cout << min(dp[root][1], dp[root][2]);return 0;
}

求出每个点的最长路径d1和次长路径d2后，树上的最长路径就是$max(d1+d2)$
状态表示$dp1[u]$
集合：以u节点为根的子树到其他节点的路径。
属性：$max$
状态计算
$dp1[u]=max(dp1[k]+w_{uk})$
$dp2[u]=max(dp1[c]+w_{uc})$$(c\ne k)$

#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010;
int tot = 1, res = 0;
int e[N * 2], ne[N * 2], w[N * 2], h[N];
int n;
void add(int a, int b, int c)
{e[tot] = b, w[tot] = c, ne[tot] = h[a], h[a] = tot ++ ;
}
int dfs(int u, int fa)
{int d1 = 0, d2 = 0, dist = 0;for (int i = h[u]; ~i; i = ne[i]){if (e[i] == fa) continue;int d = dfs(e[i], u) + w[i];dist = max(dist, d);if (d1 <= d)  d2 = d1, d1 = d;else if (d > d2) d2 = d;}res = max(res, d1 + d2);return dist;
}
int main()
{cin >> n;memset(h, -1, sizeof h);for (int i = 1; i < n; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dfs(1, -1);cout << res;return 0;
}

求出每个点u的最长路径d1和次长路径d2，一个节点到其他节点的最远距离为$max(d1,d_{fa}1)$——当路径$d_{fa}1$不经过u时；反之，最远距离就是$max(d1,d_{fa}2)$。
$d_{fa}1$为父节点到其他节点的最远距离，$d_{fa}2$为父节点到其他节点的次远距离。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010;
const int INF = 0x3f3f3f3f;
int h[N], e[N * 2], ne[N * 2], w[N * 2];
int d1[N], d2[N], up[N], p1[N], p2[N];
int tot = 1;
int n;
void add (int a, int b, int c)
{e[tot] = b, w[tot] = c, ne[tot] = h[a], h[a] = tot ++ ;
}
void dfs1(int u, int fa)
{for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (j == fa) continue;dfs1(j, u);if (d1[u] <= d1[j] + w[i]){d2[u] = d1[u], d1[u] = d1[j] + w[i];p2[u] = p1[u], p1[u] = j;}else if (d2[u] < d1[j] + w[i]){d2[u] = d1[j] + w[i];p2[u] = j;}}return ;
}
void dfs2(int u, int fa)
{for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (j == fa) continue;if (p1[u] == j) up[j] = w[i] + max(up[u], d2[u]);   //son_u  = j，则用次大更新else up[j] = w[i] + max(up[u], d1[u]);              //son_u != j，则用最大更新dfs2(j, u);}return ;
}
int main()
{cin >> n;memset(h, -1, sizeof h);for (int i = 1; i < n; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dfs1(1, -1);dfs2(1, -1);int res = INF;for (int i = 1; i <= n; i ++ ){res = min(res, max(d1[i], up[i]));}cout << res;return 0;
}

本题本质上就是acwing.1072题加上一个背景。
先求出每个数对应的约数和，对于合法的数$i$，就相当于把$i$连接在约数和$sum[i]$上,把所有数都那么操作之后就得到了一棵树，这样一来，求不断进行数字变换且不出现重复数字的最多变换步数就相当于求数的最长直径。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 50010;
int e[N], ne[N], w[N], h[N];
int sum[N];
int st[N];
int n;
int tot = 1;
int res = 0;
void add(int a, int b)
{e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
int dfs(int u)
{int d1 = 0, d2 = 0;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];int d = dfs(j) + 1;if (d >= d1) d2 = d1, d1 = d;else if (d > d2) d2 = d;}res = max(res, d1 + d2);return d1;
}
int main()
{cin >> n;memset(h, -1, sizeof h);for (int i = 1; i <= n; i ++ ){for (int j = 2; j * i <= n; j ++ )sum[i * j] += i;}for (int i = 1; i <= n; i ++ ){if (sum[i] < i){st[i] = 1;add(sum[i], i);}}for (int i = 1; i <= n; i ++ )if(st[i]) dfs(i);cout << res;return 0;
}