树的最长路径
题目链接：树的最长路径
分析：我们需要在树上DP，状态表示这一方面是比较困难的，我们要找最长的一条路径，那我们随意画一棵树
代码实现：
#include<iostream>
using namespace std;
const int N=1e4+10,M=2*N;
int n,h[N],w[M],ne[M],idx=1,e[M],ans;
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs(int u,int father){
int d1=0,d2=0;//d1记录最长的边，d2记录第2长的边
for(int i=h[u];i;i=ne[i]){//遍历所有出边
int j=e[i];
if(j==father) continue;//如果是它的父亲，就跳过，这里放止往回搜
int d=dfs(j,u)+w[i];//搜出以j为根节点的子树中最长的加上w[i]
if(d>=d1){//更新最长边和第二长边
d2=d1;
d1=d;
}
else if(d>d2){//更新第二长边
d2=d;
}
}
ans=max(ans,d1+d2);//更新答案
return d1;//返回最长的边
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);//加两条边
add(b,a,c);
}
dfs(1,0);//第二个参数随意传一个没用到的结点，第一个结点随意，因为不管从哪个结点开始，都可以转化为一棵树
printf("%d\n",ans);
return 0;
}
树的中心
题目链接：树的中心
分析：这是一道很好的树形DP题，我们可以随便选取一个点，向上遍历所有点，再向下遍历所有点，遍历的途中更新答案，详细讲解见代码。
代码实现：
代码中的细节还是比较多的
#include<iostream>
using namespace std;
const int N=1e4+10,M=2*N,INF=1e9;
int n,h[N],e[M],ne[M],w[M],idx=1;
bool is_leaf[N];
int d1[N],d2[N],p[N],up[N];//d1[i]表示从第i点往下走的最长长度，d2表示第二长长度，p表示向下的最长路径经过了哪一点（记录最近的一个点即可），up表示向上走的最长路
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs_d(int u,int father){//向下搜的话和上题差不多
d1[u]=d2[u]=0;
for(int i=h[u];i;i=ne[i]){
int j=e[i];
if(j==father) continue;
int d=dfs_d(j,u)+w[i];
if(d>=d1[u]){
d2[u]=d1[u];
d1[u]=d;
p[u]=j;
}
else if(d>=d2[u]) d2[u]=d;
}
return d1[u];
}
int dfs_u(int u,int father){//向上走
for(int i=h[u];i;i=ne[i]){
int j=e[i];
if(j==father) continue;
//这里当u是1时，up[u]=0，但这并不影响转移，因为一定去掉最长向下路后走拐向第二长一定是最长的
if(p[u]==j) up[j]=max(d2[u],up[u])+w[i];//如果从u往下走的最长路经过了j，那么j点往上走的最长路就是向上或者拐弯走向第二长向下路的路径
else up[j]=max(up[u],d1[u])+w[i];//否则只需从拐向最长向下路和向上走选一个
dfs_u(j,u);
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
dfs_d(1,0);//向下
dfs_u(1,0);//向上
int res=d1[1];//注意，本题中1号结点遍历到所有点都相当于向下走了
for(int i=2;i<=n;i++){//其它点要在向上和向下最长中取个最大值再和res取个最小值
res=min(res,max(up[i],d1[i]));
}
cout<<res<<endl;
return 0;
}
数字转换
题目链接：数字转换
分析：这道题还是比较有意思的，我们把所有能连的边都预处理出来并连上，然后就需要求最长的一条路径，回到了第一题。需要注意的是，本题可能会出现多棵树的情况，即不一定所有点都连通，因此我们对每个点都搜一遍。
代码实现：
#include<iostream>
using namespace std;
const int N=5e4+10;
int idx=1,h[N],ne[N],e[N],sum[N];
int d1[N],d2[N],res;
bool st[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
if(d1[u]) return ;//如果搜过就直接返回最长的
st[u]=1;//搜过了就标记一下
for(int i=h[u];i;i=ne[i]){
int j=e[i];
dfs(j);
if(d1[j]+1>d1[u]) d2[u]=d1[u],d1[u]=d1[j]+1;
else if(d1[j]+1>d2[u]) d2[u]=d1[j]+1;
}
res=max(res,d1[u]+d2[u]);
}
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){//先处理出所有数的约数之和
for(int j=2;j<=n/i;j++){//因为约数不包含自身，所有j从2开始
sum[i*j]+=i;
}
}
for(int i=2;i<=n;i++){//加边从2开始，否则会加一条从0到1的边
if(sum[i]<i){
add(sum[i],i);//从小的数往大的树连一条边，我们不用反向搜，所以建立一条边即可
}
}
for(int i=1;i<=n;i++){//从最小的点开始搜
if(!st[i])//如果没搜过
dfs(i);
}
cout<<res;
return 0;
}
二叉苹果树
题目链接：二叉苹果树
分析：这道题还是比较easy的，感觉到一股01背包味？再品品，感觉到一股区间DP味？或许这就是算法的美妙之处吧（你中有我，我中有你）。
代码实现：
#include<iostream>
using namespace std;
int n,q;
const int N=110,M=2*N;
int dp[N][N];//dp[i][j]表示以i为根节点的子树，保留j根树枝剩余的最大苹果数
int h[N],ne[M],w[M],idx=1,e[M];
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,int father){
for(int i=h[u];i;i=ne[i]){
if(e[i]==father) continue;
dfs(e[i],u);
for(int j=q;j;j--){//枚举以u为根节点保留的树枝数量
for(int k=0;k<j;k++){//枚举以该子节点为根节点的子树保留的树枝数量
dp[u][j]=max(dp[u][j],dp[e[i]][k]+dp[u][j-k-1]+w[i]);
}
}
}
}
int main(){
cin>>n>>q;
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,0);
cout<<dp[1][q];
return 0;
}
战略游戏
题目链接：战略游戏
分析：一股子状态机模型味，就按照那个模型写吧，详见代码。
代码实现：
#include<iostream>
#include<cstring>
using namespace std;
const int N=1510;
int n;
int h[N],e[N],ne[N],idx=1;
int dp[N][2];//dp[i][0]表示在i处不放时的最小值，1时放置
bool vis[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){
dp[u][0]=0,dp[u][1]=1;
for(int i=h[u];i;i=ne[i]){
int j=e[i];
dfs(j);
dp[u][0]+=dp[j][1];//若u结点不放置，子节点必须放置
dp[u][1]+=min(dp[j][0],dp[j][1]);//若u结点放置，子节点可以放可以不放
}
}
int main(){
while(scanf("%d",&n)!=-1){
memset(h,0,sizeof h);
idx=1;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++){
int a,b;
scanf("%d:(%d)",&a,&b);
while(b--){
int c;
scanf("%d",&c);
add(a,c);
vis[c]=true;//不是根节点的标记一下
}
}
int root=0;
while(vis[root]) root++;//找出根节点
dfs(root);
printf("%d\n",min(dp[root][0],dp[root][1]));
}
return 0;
}
皇宫看守
题目链接：皇宫看守
分析：注意，本题和上题不一样，上题是观察边，本题是观察点，但其实思路都差不多，详见代码。
代码实现：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1510;
int n;
int h[N], w[N], e[N], ne[N], idx;
int f[N][3];//f[i][0]表示第i点被它的父节点观察到，f[i][1]表示被它的子节点看住，f[i][2]表示被自己看住
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][2] = w[u];
int sum = 0;
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]);//如果此节点自己看着，那么它的子节点可以随意
sum += min(f[j][1], f[j][2]);//sum求f[u][1]时会用，此状态下所有子节点都必须依靠自己或儿子，累加起来
}
f[u][1] = 1e9;//对于f[u][1]，我们要选一个最好的子节点，因此初始化为很大的数，然后取最小的情况的值
for (int i = h[u]; ~i; i = ne[i]){//枚举所有子节点，该子节点放置上守卫，则总价钱要减去min(f[j][1], f[j][2])再加上f[j][2]
int j = e[i];
f[u][1] = min(f[u][1], sum - min(f[j][1], f[j][2]) + f[j][2]);
}
}
int main(){
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ){
int id, cost, cnt;
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);
cout << min(f[root][1], f[root][2]) << endl;
return 0;
}
树形DP的题感觉还都是很有意思的，还要在洛谷上多刷刷题！