树形dp瞎讲+树形dp基础题题解

---恢复内容开始---

没错

咕了这么久（没有青青姐久

我又开始写博客了( ´▽｀)

想了很久些什么（才没有想过呢

虽然被鄙视基础不好但还是走上了树形dp的不归路

那么

就来写写树形dp吧（dtx daolao不要打我

树形dp是什么呢？

一言概之，dfs中的动态规划

emmmmm

对

因为没什么固定格式

就推转移方程（所以我一开始根本找不到讲树形dp的blog

然后发现了良心博客一枚

放一下链接

基本的 $d p$

选择节点类
$d p [i] [0] = d p [j] [1]$ $d p [i] [1] = max / min (d p [j] [0]$
树形背包类
$d p [v] [k] = d p [u] [k] + v a l$ $d p [u] [k] = m a x (d p [u] [$

虽然关于树形dp的博客基本上都是题

但是看懂了基本dp方程，理解了实质大概就不会特别难（我这句话真严谨

然后

题还是有很多的

就不放题面了

放链接好了

（要是放一堆图片有假装写了很多的嫌疑

传送门——>luogu P1352 没有上司的舞会

核心的代码就是上边放的状态转移方程

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 6010

int fa[maxn],dp[maxn][2];
int root,n;
int v[maxn];
int nxt[maxn],head[maxn];

void treedp(int x){
    for(int i = head[x];i;i = nxt[i]){
        treedp(i);
        dp[x][0] += max(dp[i][1],dp[i][0]);//dp[x][0]代表上司x不来时的最大快乐指数
        dp[x][1] += dp[i][0];//dp[x][1]代表上司来的
    }
}

int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
        scanf("%d",&dp[i][1]);
    for(int i = 1; i < n; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x] ++;//记录一下有没有上司
        nxt[x] = head[y];
        head[y] = x;//对，像链式前向星的东西（我还理解了好久【划掉
    }
    for(int i = 1; i <= n; i++)
        if(!v[i]) {//没有上司的就是最大上司啦
            root = i;
            break;
        }
    treedp(root);//从树根开始dp
    printf("%d",max(dp[root][0],dp[root][1]));//取最高上司来和不来的最大快乐指数
    return 0;
}

emmmmm

还是蛮好懂的吧

然后上下一道

传送门 ———>luogu P1122 最大子树和

这里有一点点的变化

就是剪掉了之后是加0

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 16010

int dp[maxn];
int cnt,head[maxn * 2];
int f[maxn];//记录当前子节点到之下的花的最大值
int ans = -2147483647;//因为可能全是负的所以ans搞到最小

struct EDGE{
  int nxt,to;
}edge[maxn * 2];

void add(int x,int y){
  edge[++cnt].to = y;
  edge[cnt].nxt = head[x];
  head[x] = cnt;
}//正常的加边看上去真舒服啊

void treedp(int u,int fa){
  f[u] = dp[u];//给f[u]赋值为它本身的大小
  for(int i = head[u];i;i = edge[i].nxt){
    int v = edge[i].to;//v是u的儿子
    if(v != fa){//唔防止双向加边跑回去
      treedp(v,u);
      f[u] += max(0,f[v]);
    }
  }
  ans = max(ans,f[u]);//反正所有的花都在一根上不需要加和什么的（我在说什么废话
}

int main(){
  int n;
  scanf("%d",&n);
  for(int i = 1;i <= n;i++)
    scanf("%d",&dp[i]);
  for(int i = 1;i < n;i++){
    int x,y;
    scanf("%d%d",&x,&y);
    add(x,y);
    add(y,x);
  }
  treedp(1,0);//将1的父节点定义为0
  printf("%d",ans);
  return 0;
}

唔嗷【好困

（明天的联欢是我写博客的动力【不小心暴露了什么

下一道来

传送门———>luogu P2016 战略游戏

（吓死我了插链接的时候突然闪退了(╥﹏╥)还好有自动保存这种可爱的东西

emmmm

这道题似乎又回到了原点？

其实跟没有上司的舞会很像

就是上司不来，下属必须来

上司来，下属来不来都行

（有点像开会？总得来一个负责人，当然都希望来的越少越好了【因为懒

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1510

struct EDGE{
  int nxt,to;
}edge[maxn];

int cnt,head[maxn];
int v[maxn];
int dp[maxn][2];

void add(int x,int y){
  edge[++cnt].to = y;
  edge[cnt].nxt = head[x];
  head[x] = cnt;
}

void treedp(int x){
  dp[x][1] = 1;//放的地方都是一
  for(int i = head[x];i;i = edge[i].nxt){
    int u = edge[i].to;
    treedp(u);
    dp[x][0] += dp[u][1];//当前点不放，下一个点一定要放
    dp[x][1] += min(dp[u][1],dp[u][0]);当前放了下一个点不一定放不放
  }
}

int main(){
  int n;
  scanf("%d",&n);
  for(int i = 0;i < n;i++){
    int r,k;
    scanf("%d%d",&r,&k);
    for(int j = 0;j < k;j++){
      int p;
      scanf("%d",&p);
      v[p]++;
      add(r,p);
    }
  }
  int root;
  for(int i = 0;i < n;i++)
    if(!v[i]){
      root = i;
      break;
    }//唔又是找根
  treedp(root);
  printf("%d",min(dp[root][0],dp[root][1]));
  return 0;
}

啊友情提示

a掉这道题之后可以顺道a掉luogu UVA1292 Strategic game

差别就是这道题要输入多组数据而已

emmmmm

去写选课

写完就发

好的我鸽了

告辞【快速溜

树形dp瞎讲+树形dp基础题题解

基本的dp方程

选择节点类

树形背包类

基本的 $d p$