树形 DP

题型多而杂，我们通过学习例题的方式看一下。

T1：树的直径

考虑树形 DP。

对于每一个子树，我们都可以求出在该子树的最长路径。

对于根节点，他的所有儿子都会有一个向下的最大路径。

然后，我们维护这些路径的最大值和次大值，就可以求出经过该点且在该点里的最大路径。

T2：树的中心

直接考虑怎样求从一个点出发走到的最远距离。

对于一个点，他向下走的最大距离是很好求的，直接模仿上一题。

接下来，我们考虑向上走。

首先，走到父亲节点时，他有两种选择：继续向上走或者向下走。

向上走的部分就可以递归了，但是向下走有问题：如果向下的最大距离是经过当前点怎么办？

我们再维护一个次大值，向下的最大路径如果经过当前点的话，就给次大值。

T3：数字变换

题目传送门 LOJ

将问题抽象为一颗树的形式：假设较小的数是较大的数的父亲。

那么，每一个数，一定只有一个父亲，且一定不会形成一个环。

所以，按小到大的顺序建好树后，就可以直接求树的直径了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5e4+10,M=1e5+10,INF=0x3f3f3f3f;
int h[N],e[M],ne[M],idx;
int sum[N],d[N],ans,n;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int x)
{
    if (d[x]>=0) return d[x];
    int &d1=d[x],d2=-INF;
    for (int i=h[x];~i;i=ne[i])
    {
        int t=dfs(e[i])+1;
        if (t>=d1) d2=d1,d1=t;
        else if (t>d2) d2=t;
    }
    ans=max(ans,d1+d2);
    // printf("%d %d %d\n",x,d1,d2);
    if (d1<0) d1=0;
    return d1;
}

int main()
{
    memset(h,-1,sizeof h);
    memset(d,0xcf,sizeof d);
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        for (int j=2;j<=n/i;++j) sum[i*j]+=i;
    for (int i=1;i<=n;++i)
        if (sum[i]<i) add(sum[i],i);
    for (int i=1;i<=n;++i)
        if (d[i]<0) dfs(i);
    printf("%d\n",ans);
    return 0;
}

T4：二叉苹果树

题目传送门 LOJ

这个是一个比较简单的树形（有依赖的）背包问题。

考虑计算一个节点。

对于他的所有儿子来说，都相当于是一个分组的物品。

直接分组背包即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=150,M=300;
int h[N],e[M],ne[M],w[M],idx;
int n,k,f[N][N];

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void dfs(int x,int fa)
{
    for (int i=h[x];~i;i=ne[i])
    {
        if (e[i]==fa) continue;
        dfs(e[i],x);
        for (int j=k;j;--j)
            for (int l=0;l+1<=j;++l)
                f[x][j]=max(f[x][j],f[x][j-l-1]+f[e[i]][l]+w[i]);
    }
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d %d",&n,&k);
    for (int i=1,x,y,c;i<n;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        add(x,y,c);add(y,x,c);
    }
    dfs(1,-1);
    cout<<f[1][k]<<endl;
    return 0;
}

T5：战略游戏

题目传送门 LOJ

记录 $f[i,0]$ 为 $i$ 节点不放士兵的最小代价，$f[i,1]$ 为 $i$ 节点放士兵的最小代价。

那么，就可以得到：

$$f[i,1]=\sum_{(i,j)\in E}{\min (f[j,0],f[j,1])}$$ $$f[i,0]=\sum_{(i,j)\in E}{f[j,1]}$$

就可以计算了。

（话说我尝试了一下新型的码风）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1505, M = 2 * N;
int h[N], e[M], ne[M], idx;
int n, f[N][2];
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int x)
{
    f[x][1] = 1;
    for (int i = h[x]; ~i; i = ne[i])
    {
        dfs(e[i]);
        f[x][0] += f[e[i]][1];
        f[x][1] += min(f[e[i]][0], f[e[i]][1]);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i )
    {
        int b, id, tot;
        scanf("%d %d", &id, &tot);

        while (tot -- )
        {
            scanf("%d", &b);
            add(id, b);
            st[b] = true;
        }
    }
    
    int rt = 0;
    while (st[rt]) rt ++ ;
    dfs(rt);

    printf("%d\n", min(f[rt][1], f[rt][0]));

    return 0;
}

T6：皇宫看守

题目传送门 LOJ

这个题大概要使用到状态自动机模型（但是我没写）

其实也不难，就是不同的状态之间的转化。

设 $0$ 状态为儿子节点看守本节点， $1$ 状态为本节点看守，$2$ 状态为父亲节点看守。

每一个节点的三种状态，都可以通过儿子节点算出来。

具体请读者自行实现，或者看代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1505, M = 2 * N;
int h[N], e[M], ne[M], idx;
int f[N][3], v[N], n;
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int x)
{
    f[x][1] = v[x];
    for (int i = h[x]; ~i; i = ne[i])
    {
        dfs(e[i]);
        f[x][1] += min(min(f[e[i]][1], f[e[i]][2]), f[e[i]][0]);
        f[x][2] += min(f[e[i]][1], f[e[i]][0]);
    }
    int tot = 0;
    for (int i = h[x]; ~i; i = ne[i])
        tot += min(f[e[i]][1], f[e[i]][0]);
    f[x][0] = 0x3f3f3f3f;
    for (int i = h[x]; ~i; i = ne[i])
        f[x][0] = min(f[x][0], tot - min(f[e[i]][1], f[e[i]][0]) + f[e[i]][1]);
    // printf("%d %d %d %d\n", x, f[x][0], f[x][1], f[x][2]);
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);

    for (int i = 0;i < n; ++ i )
    {
        int id, b, tot;
        scanf("%d", &id);
        scanf("%d %d", &v[id], &tot);
        while (tot -- )
        {
            scanf("%d", &b);
            add(id, b);
            st[b] = true;
        }
    }

    int rt = 1;
    while (st[rt]) rt ++ ;
    dfs(rt);

    printf("%d\n",min(f[rt][0],f[rt][1]));

    return 0;
}