p153200怎么解决（P1352 没有上司的舞会+P1122 最大子树和（树形DP入门））

前言

今日偶然打开 \(oi-wiki\)   
    
    
    
，发现树形 \(DP\) 例题正好是之前在洛谷上鸽着的一道题   
    
    
    
。所以......

\(\color{red}{很高兴以这样的方式认识你


     


     


     


   ，树形 DP !}\)

这例题造的太好了 




 




 




 

，简直是无痛入门（感动.jpg）

P1352 没有上司的舞会

题目传送门~

思路剖析

状态定义

\(dp_i\) 表示的是以 \(i\) 为根节点的子树所获得的最大价值


     


     


     


   。

由于每个节点代表着一位人物   

   

   

   

，有来与不来两种状态

     

     

     

  ，所以再加一维状态变量 




 




 




 

。

\(dp_{i,0}\) 表示以 \(i\) 为根节点的子树所能获得的最大价值
  




  




  




  
，且这位人物没来   

   

   

   

。 \(dp_{i,1}\) 则对应来了的状态

     

     

     

  。

状态转移方程 现在有个周年庆宴会  


  


  


  


，宴会每邀请来一个职员都会增加一定的快乐指数 r_i
  




  




  




  
。 但是呢 
     
     
     
 ，如果某个职员的直接上司来参加舞会了

   




   




   




   ，那么这个职员就无论如何也不肯来参加舞会了  


  


  


  


。

根据题意描述 



 



 



 



，容易得出状态转移方程：

\(dp_{i,0} += max (dp_{j,0},dp_{j,1})\)

\(dp_{i,1} += dp_{j,0}\)

\(j\) 指的是 \(i\) 的子节点                 ，且显然 \(dp_{i,1}\) 的初始值为 \(r_i\) 
     
     
     
 。

code

点击查看代码 #include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,a[6005]; int head[6005],nex[6005],edge[6005],tot; int vis[6005],dp[6005][2]; void dfs(int x){ dp[x][1]=a[x]; for(int i=head[x];i;i=nex[i]){ int y=edge[i]; dfs(y); dp[x][1]+=dp[y][0]; dp[x][0]+=max(dp[y][0],dp[y][1]); } return; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<n;i++){ int l,k; scanf("%d%d",&l,&k); nex[++tot]=head[k]; head[k]=tot; edge[tot]=l; vis[l]=1; } for(int i=1;i<=n;i++){ if(!vis[i]){ dfs(i); cout<<max(dp[i][0],dp[i][1])<<endl; return 0; } } }

P1122 最大子树和

题目传送门~

思路剖析

谁是根节点

由于这题是无向图（但由于以 \(n-1\) 条边相连接


    




    




    




    ，所以本质与树并无太大区别）


















，所以要讨论以谁作为根节点

   




   




   




   。

根节点之所以重要                  ，是因为在递归过程中


     



     



     



    ，我们已经默认根节点所代表的那束花已经被保留了

















，但根节点代表的花不一定在最优解的集合之中 



 



 



 



。

仔细模拟后   
    
    
    
，不难发现


     


     


     


   ，对于以 \(i\) 为根节点的子树 




 




 




 

，\(dp_i\) 往下为最优解   

   

   

   

，而往上由于还未更新

     

     

     

  ，因此相当于剪去 \(dp_i\) 与其根节点的枝桠                 。

进一步推理
  




  




  




  
，无论通过哪个节点作为根节点  


  


  


  


，再递归的过程中 
     
     
     
 ，其实已经变相枚举了将其剪去的种种情况

   




   




   




   ，所以 



 



 



 



，只需要在过程中取最优解即可


    




    




    




    。

状态定义+状态转移方程

这点比较好理解                 ，所以合并在一起阐述


















。

\(dp_i\) 表示以 \(i\) 为根节点的子树所获得的最大美丽值                  。

显然有

\(dp_i+=max(dp_j,0)\)


     



     



     



    。

\(j\) 为子节点


    




    




    




    ，当其所带来的价值为负数时


















，不如直接剪掉

















。

code

有几处雷点在注释中标记出来了（都是血泪教训啊QAQ）

点击查看代码 #include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,ans=-0x3f3f3f3f;//答案可能为负！要初始化为负无穷 int head[16005],nex[35005],edge[35005],tot;//由于是双向边                  ，所以空间要开双倍 int dp[16005],vis[16005]; void dfs(int x){ vis[x]=1;//不要在循环内标记


     



     



     



    ，否则标记不到根节点本身   
    
    
    
。 for(int i=head[x];i;i=nex[i]){ int y=edge[i]; if(vis[y]) continue; dfs(y); if(dp[y]<=0) continue; dp[x]+=dp[y]; } ans=max(ans,dp[x]); return; } void add(int l,int k) {nex[++tot]=head[k],head[k]=tot,edge[tot]=l;} int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&dp[i]); for(int i=1;i<n;i++){ int l,k; scanf("%d%d",&l,&k); add(l,k); add(k,l); } dfs(1); cout<<ans<<endl; return 0; }

第 \(7   
    
    
    
、8\) 道

















，(‾◡◝)


     


     


     


   。

加油！