1. 树的最长路径

定义：树中两个点直接的最远距离称为树的直径

先说一个结论
先任意找到一个树中一个点u，找到距离u最远的一个点v，那么v一定是树的直径（树的直径不唯一）的一个端点。

将树的直径的集合转换为且以某个顶点为一条路径的最高点的集合。
那么就可以枚举每个顶点，当前顶点为路径的最高一个顶点，路径只能往下面延伸。这样。最长路径一定会在这个集合里面。

//要找到一条路径，使得使得路径两端的点的距离最远。
//枚举所有根节点，找到当前根节点的所有子树里面最长的和第二长的路径。
//使用dfs，第一得出推导式。第二从最底层开始看看行不行，如果可以，再看看倒数第二层，如果可以，那么就可以。#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=10010,INF=0x3f3f3f3f;
int head[N*2];
int e[N*2];
int ne[N*2];
int w[N*2];
int f[N][2];
int idx;
int n;
int res=0;void add(int a,int b,int c)
{e[idx]=b;ne[idx]=head[a];w[idx]=c;   //w[a]==w[b]==w[a,b];head[a]=idx++;
}void dfs(int u,int father)
{//dfs先考虑边界条件，因为叶子节点向下没有边，所以为0//所以初始化为0f[u][1]=f[u][0]=0; //表示最长和次长的边都是0for(int i=head[u];i!=-1;i=ne[i]){int j=e[i];if(j==father)continue;  //不能走回路dfs(j,u);if(f[j][1]+w[i]>=f[u][1])  //u的子树里面的最长边加上（u,j)这条边大于u的最长边，更新最大和次长边。{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];}}res=max(res,f[u][1]+f[u][0]);  //更新最大值。
}int main()
{cin>>n;memset(head,-1,sizeof head);for(int i=0;i<n-1;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}dfs(1,-1);cout<<res<<endl;return 0;
}

2.树的中点.

任意一个点u，它有两种情况，要么以u为起点向下延伸找到最长距离，要么往上面延伸找到最长距离。
往下面找很简单。关键是往上面找，那么就需要先dfs找一下每个顶点的最长路径和次长路径。然后再一次dfs来求出每个顶点往上面（父节点）搜索的最长路径。
最后每个顶点比较一下往上面和往下面搜索的最长距离。最终找到最长距离的最小值

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10010,M=N*2,INF=0x3f3f3f3f;int head[N];
int e[M];
int ne[M];
int idx;
int w[M];
int n;
int d1[N],d2[N],up[N];
int s[N];void add(int a,int b,int c)
{e[idx]=b;ne[idx]=head[a];w[idx]=c;head[a]=idx++;
}
void dfs(int u,int father)
{d1[u]=d2[u]=-INF;for(int i=head[u];i!=-1;i=ne[i]){int j=e[i];if(j==father)continue;dfs(j,u);if(d1[j]+w[i]>=d1[u]){d2[u]=d1[u];d1[u]=d1[j]+w[i];s[u]=j;  //点u地最长地子树地第一个节点是j}else if(d1[j]+w[i]>d2[u]){d2[u]=d1[j]+w[i];}}if(d1[u]==-INF){d1[u]=d2[u]=0;}
}void dfs_1(int u,int father)
{for(int i=head[u];i!=-1;i=ne[i]){int j=e[i];if(j==father)continue;if(j==s[u])  //那么j不能走，只能走右边{up[j]=max(up[u],d2[u])+w[i];}else{up[j]=max(up[u],d1[u])+w[i];}dfs_1(j,u);}
}int main()
{cin>>n;memset(head,-1,sizeof head);for(int i=0;i<n-1;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}//先找每个节点往下面的最长距离和次长距离dfs(1,-1);dfs_1(1,-1);int res=INF;for(int i=1;i<=n;i++){res=min(res,max(d1[i],up[i]));}cout<<res;return 0;}

由于第三题需要用到一些数学地知识，所以先去补一补数学知识。连接链接在这里

4.二叉苹果树

先去看有依赖的背包问题（模板题）

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N=110,INF=0x3f3f3f3f;
int head[N],e[N*2],ne[N*2],w[N*2];
int idx;
int n,m;
int f[N][N];void add(int a,int b,int c)
{e[idx]=b;ne[idx]=head[a];w[idx]=c;head[a]=idx++;
}void dfs(int u,int father)   //表示以u为根节点，找到体积为j的最大价值
{for(int i=head[u];i!=-1;i=ne[i])  //枚举物品组{int son=e[i];if(son==father)continue;dfs(son,u);   //找到当前节点子树的各个体积的最大价值for(int j=m;j>=0;j--)  //枚举体积{for(int k=0;k<j;k++)   //决策，也就是看给当前子树分配多少空间可以使得以u为根节点总价值最大{f[u][j]=max(f[u][j],f[son][k]+w[i]+f[u][j-k-1]);   //父亲节点一定要选，所以孩子节点的体积最大只能选j-1}}}
}
int main()
{cin>>n>>m;memset(head,-1,sizeof head);for(int i=0;i<n-1;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);}dfs(1,-1);cout<<f[1][m]<<endl;return 0;
}

5.战略游戏

本题思路：可以先去看“没有上司的舞会”一题。树形dp+状态机

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;const int N=1510,M=N*2;int head[N],e[M],ne[M],w[M];
int idx;
int n;
int f[N][2];   //f[i][0]表示i为根节点的子树且i不选的最小摆放士兵
bool st[N];  //找父节点void add(int a,int b)
{e[idx]=b;ne[idx]=head[a];head[a]=idx++;
}void dfs(int u)   //有像图，不用father节点
{//考虑最底层的dfs，叶子节点.f[u][1]=1,f[u][0]=0;for(int i=head[u];i!=-1;i=ne[i]){int j=e[i];dfs(j);f[u][0]+=f[j][1];f[u][1]+=min(f[j][0],f[j][1]);}}int main()
{while(scanf("%d",&n)!=-1){memset(head,-1,sizeof head);memset(st,0,sizeof st);idx=0;for(int i=0;i<n;i++){int id,cnt;scanf("%d:(%d)",&id,&cnt);while (cnt -- )    //当前节点的子节点{int ver;scanf("%d", &ver);add(id, ver);st[ver] = true; // ver 有父节点}}//找根节点int root=0;while(st[root])   //由于节点编号是0-n-1,所以从0开始找，0不一定是根节点，要注意{root++;}dfs(root);int res=min(f[root][0],f[root][1]);cout<<res<<endl;}
}

6.皇宫守卫

#include <iostream>
#include <cstring>
using namespace std;/*
以下注释为早期笔记，希望对你有所帮助状态机 + 树形Dp问题
状态表示:f(i, 0)：第i号结点被他的父结点安排的守卫看住的方案数f(i, 1)：第i号结点被他的子结点安排的守卫看住的方案数f(i, 2)：第i号结点自己安排守卫看住的方案数
状态计算:(j是i的子结点)f(i, 0) = sum{min(f(j,1), f(j,2))}i是被他父结点看住的，那他的子结点要么自己看自己，要么被自己的子结点看住f(i, 1) = min{w(k) + f(k, 2) - sum{min(f(j,1), f(j,2))}}i如果是被子结点看住的，那么就要枚举他是被哪个子结点看住的所有方案，对所有方案求最小值这里的sum不包括j==k的情况，因此需要手动额外减去f(i, 2) = sum{min(f(j,0), f(j,1), f(j,2))} + w(u)i是被自己看住的，那他的子结点可以被父结点看住，可以自己看自己，也可以被自己的子结点看住
*/
const int N = 1510;
int n;
int h[N], w[N], e[N], ne[N], idx;
int f[N][3];
bool st[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {f[u][0] = 0;f[u][1] = 1e9; //f[u][1]求最小值，初始化为最大值f[u][2] = w[u];//初始化放置自己的代价for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];dfs(j);f[u][0] += min(f[j][1], f[j][2]);f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);}for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];//f[u][0]中记录了sum{min(f(j,1), f(j,2))}，再从中减去对应的贡献即可得到remain verf[u][1] = min(f[u][1], f[u][0] + f[j][2] - min(f[j][1], f[j][2]));}
}
int main() {memset(h, -1, sizeof h);cin >> n;for (int i = 1; i <= n; ++i) {int id, cnt, cost;cin >> id >> cost >> cnt;w[id] = cost;while (cnt--) {int ver;cin >> ver;add(id, ver);st[ver] = true;}}int root = 1;while (st[root]) ++root;dfs(root);printf("%d\n", min(f[root][1], f[root][2]));return 0;
}