关于树形dp

我觉得他和线性dp差不多

总结

最近写了好多树形dp+树形结构的题目，这些题目变化多样能与多种算法结合，但还是有好多规律可以找的。

先说总的规律吧！

     一般来说树形dp在设状态转移方程时都可以用f[i][]表示i这颗子树怎么怎么样的最优解，实现时一般都是用子树更新父亲（即从下向上更新），
那么首先应该考虑的是一个一个子树的更新父亲还是把所有子树都算完了再更新父亲？这就要因题而异了，一般来说有两种情况：
      1.需要把所有子树的信息都掌握之后再更新子树的就需要把所有子树都算完了在更新父亲。
      2.而像树上背包这样的问题就需要一个一个的更新，每次都用一个子树更新已经更新完的子树+父亲，最后就可以将这一部分的子树更新完了，
再继续往上更新，最后根节点就是答案。

题目

P1352 没有上司的舞会

这道题就画个树再列一下方程就可以了

之前主要是在回顾链式前向星（逃

#include <bits/stdc++.h>
using namespace std;
int a[6010];
struct node
{
    int to,nxt;
}e[6010];
int ecnt,ehead[6010];
void add(int a,int b)
{
    e[++ecnt] = (node){b,ehead[a]};
    ehead[a] = ecnt;
}
bool flag[6010];
int f[6010][2];
void work(int root)
{
    f[root][0]=0;
    f[root][1]=a[root];
    for(int i=ehead[root];i;i=e[i].nxt)
    {
        int to=e[i].to;
        work(to);
        f[root][0]+=max(f[to][0],f[to][1]);
        f[root][1]=max(f[root][1],f[root][1]+f[to][0]);
    }
    return;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n-1;i++)
    {
        int l,k;
        scanf("%d%d",&l,&k);
        add(k,l);
        flag[l]=true;
    }
    for(int i=1;i<=n;i++)

        if(flag[i]==false)
        {
            work(i);
            printf("%d",max(f[i][0],f[i][1]));
            break;
        }
    return 0;
}

P1122最大子树和

也不难，主要是如果子树是负数就不要了

#include<bits/stdc++.h>
using namespace std;
int hd[100005];
struct node{
    int net,to;
}tree[100005];
int a[100005],n;
int f[100005],cnt=0;
int ans=0;
int add(int x,int y){
    ++cnt;
    tree[cnt].net=hd[x];
    tree[cnt].to=y;
    hd[x]=cnt;
}
int dfs(int u,int fa){
    f[u]=a[u];
    for (int i=hd[u];i;i=tree[i].net){
        int v=tree[i].to;
        if (v!=fa){
            dfs(v,u);
            f[u]+=max(0,f[v]);
        }
    }
    ans=max(ans,f[u]);
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int x,y;
    for (int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}

P2016 战略游戏

其实是和《没有上司的舞会》差不多的只是判断一下路径就好了

#include <bits/stdc++.h>
using namespace std;
const int N=1500,M=1500;
int n,m,root,num_edge,head[N+1],f[N+1][2];
struct Edge{
    int next,to;
}edge[2*M+2];
void Add_edge(int from,int to) {edge[++num_edge]=(Edge){head[from],to},head[from]=num_edge;}
inline int min(int fa,int fb){return fa<fb?fa:fb;}
int Dp(int u,int fa)
{
    f[u][1]=1,f[u][0]=0;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v!=fa) Dp(v,u),f[u][0]+=f[v][1],f[u][1]+=min(f[v][0],f[v][1]);
    }
}
int main()
{
    int from,to,cnt;
    scanf("%d",&n);
    memset(f,127,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&from,&cnt);
        for (int j=1;j<=cnt;j++) scanf("%d",&to),Add_edge(from,to),Add_edge(to,from);
    }
    root=1,Dp(root,-1);
    printf("%d",min(f[root][0],f[root][1]));
    return 0;
}

P1922 女仆咖啡厅桌游吧

思路：树形DP。因为每一个非叶子结点的子树的状态都是唯一的确定的，所以只需要把某个节点的儿子中叶子节点的个数统计出来。

#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n,m,tot;
int dad[MAXN],f[MAXN];
int l[MAXN],num[MAXN];
int to[MAXN*2],net[MAXN*2],head[MAXN];
void add(int u,int v){
    to[++tot]=v;net[tot]=head[u];head[u]=tot;
    to[++tot]=u;net[tot]=head[v];head[v]=tot;
}
void dfs(int now){
    l[now]=1;
    for(int i=head[now];i;i=net[i])
        if(to[i]!=dad[now]){
            dad[to[i]]=now;
            dfs(to[i]);
            if(l[to[i]]==1)    num[now]+=1;
            else f[now]+=f[to[i]];
            l[now]+=l[to[i]];
        }
    f[now]+=(num[now]+1)/2;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    dfs(1);
    cout<<f[1];
}