首页 > 其他分享 >树形 dp

树形 dp

时间:2023-08-15 19:56:02浏览次数:38  
标签:nxt int eg 树形 MAXN sum dp

树形 dp

概念

  • 在树上做 dp
  • 树形 dp 一般是从树的叶子节点向根的做 dp,也就是自下而上做 dp

树上 dp 加差分统计

  • 记住差分,在做很多树上的统计题时,都会用到
点击查看代码
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXN = 2e5 + 3;

int n, ANS = 0;
int dp[MAXN][3];
vector<int> eg[MAXN];

void dfs(int x, int dad){
  for(int nxt : eg[x]){
    if(nxt == dad) continue;
    dfs(nxt, x);
    dp[x][0] += max(dp[nxt][0], dp[nxt][1]);
  }
  for(int nxt : eg[x]){
    if(nxt == dad) continue;
    dp[x][1] = max(dp[x][1], dp[x][0] - max(dp[nxt][0], dp[nxt][1]) + dp[nxt][0] + 1);
  }
}

int main(){
  cin >> n;
  for(int i = 1, U, V; i < n; i++){
    cin >> U >> V;
    eg[U].push_back(V);
    eg[V].push_back(U);
  }
  dfs(1, 0);
  cout << max(dp[1][1], dp[1][0]);
  return 0;
}

树上 dp 记录最大值、次大值

  • 需要注意记录最大值、次大值时的细节
  • 有时还需要两个 \(pair\) 结合求最大值、次大值,那样细节会更加的多
  • 记录最大值、次大值,在做很多树上的 dp 时,都会用到
点击查看代码
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXN = 2e5 + 3;

int n, ANS = 0;
int ans[MAXN];
int dp[MAXN][3];
vector<int> eg[MAXN];

void dfs(int x, int dad){
  for(int nxt : eg[x]){
    if(nxt == dad) continue;
    dfs(nxt, x);
    if(dp[x][1] <= dp[nxt][1] + 1){
      dp[x][2] = dp[x][1];
      dp[x][1] = dp[nxt][1] + 1;
    }else{
      dp[x][2] = max(dp[x][2], dp[nxt][1] + 1);
    }
  }
  //cout << x << " " << dp[x][1] << " " << dp[x][2] << "\n";
  ANS = max(ANS, dp[x][1] + dp[x][2]);
}

int main(){
  cin >> n;
  for(int i = 1, U, V; i < n; i++){
    cin >> U >> V;
    eg[U].push_back(V);
    eg[V].push_back(U);
  }
  dfs(1, 0);
  cout << ANS;
  return 0;
}

树形 dp 分类讨论

  • 这种题目要多写,可以发现其中的套路
  • 一般这种题由两种
    • 要推导公式,要差分,主要是数学 例题 1
    • 其中的某一个值要么很大,要么很小,从这个突破口来设计状态 例题 2
点击查看例题 1 代码
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXN = 1e6 + 3;
const LL mod = 998244353;

int n;
LL dp[MAXN][4];
/*
0: 被删除
1:没有被删除且还没有连点
2: 没有被删除且有连点
*/
vector<int> eg[MAXN];

LL qpow(LL A, LL B){
  LL sum = A, ANS = 1;
  for(int i = 0; i < 60; i++){
    if((B >> i) & 1){
      ANS = (ANS * sum) % mod;
    }
    sum = (sum * sum) % mod;
  }
  return ANS;
}

void dfs(int x, int dad){
  dp[x][0] = dp[x][1] = 1;
  for(int nxt : eg[x]){
    if(nxt == dad) continue;
    dfs(nxt, x);
  }
  LL sum = 1;
  for(int i = 0; i < eg[x].size(); i++){
    int nxt = eg[x][i];
    if(nxt == dad) continue;
    sum *= (dp[nxt][2] + dp[nxt][1] + dp[nxt][0]) % mod;
    sum %= mod;
    dp[x][0] *= (dp[nxt][2] + dp[nxt][0]) % mod;
    dp[x][0] %= mod;
    dp[x][1] *= dp[nxt][0] % mod;
    dp[x][1] %= mod;
  }
  dp[x][2] = (sum - dp[x][1] + mod) % mod;
}

void work(){
  cin >> n;
  for(int i = 1; i <= n; i++) eg[i].clear();
  for(int i = 1, U, V; i < n; i++){
    cin >> U >> V;
    eg[U].push_back(V);
    eg[V].push_back(U);
  }
  dfs(1, 0);
  cout << (dp[1][0] + dp[1][2]) % mod << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while(T--){
    work();
  }
  return 0;
}
点击查看例题 2 代码
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXN = 1e5 + 3;

int n, t[MAXN];
LL a[MAXN];
LL dp[MAXN][3];
vector<int> eg[MAXN];

void dfs(int x, int dad){
  LL sum = 0, MAX1 = 0, MAX2 = 0;
  for(int nxt : eg[x]){
    if(nxt == dad) continue;
    dfs(nxt, x), sum += dp[nxt][1];
    if(t[nxt] == 3){
      if(a[nxt] >= a[MAX1]){
        MAX2 = MAX1, MAX1 = nxt;
      }else if(a[nxt] >= a[MAX2]){
        MAX2 = nxt;
      }
    }
  }
  dp[x][0] = a[x], dp[x][2] = a[x] + sum;
  for(int nxt : eg[x]){
    if(nxt == dad) continue;
    dp[x][0] = max(dp[x][0], dp[nxt][0] + a[x] + (sum - dp[nxt][1]));
    int p = (MAX1 == nxt ? MAX2 : MAX1);
    if(p > 0){
      dp[x][0] = max(dp[x][0], dp[nxt][2] + a[x] + sum - dp[nxt][1] + a[p]);
    }
  }
  dp[x][1] = dp[x][0] - a[x];
}

void work(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    cin >> t[i], eg[i].clear();;
  }
  for(int i = 1, U, V; i < n; i++){
    cin >> U >> V;
    eg[U].push_back(V);
    eg[V].push_back(U);
  }
  dfs(1, 0);
  cout << dp[1][0] << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  int T;
  cin >> T;
  while(T--) work();
  return 0;
}

标签:nxt,int,eg,树形,MAXN,sum,dp
From: https://www.cnblogs.com/huangqixuan/p/17632283.html

相关文章

  • TCP和UDP
    一、进程间通信-socket套接字基本特征:socket是一种接口技术,被抽象了一种文件操作,可以让同一计算机中的不同进程之间通信,也可以让不同计算机中的进程之间通信(网络通信)本地进程间通信编程模型:进程A进程B创建socket对象创建sock......
  • ThingsKit物联网平台设备UDP接入
    入门介绍UDP基础知识UDP是UserDatagramProtocol(用户数据协议)的简称,是一种无连接的协议,该协议工作在OSI模型中的第四层(传输层),处于IP协议的上一层。传输层的功能就是建立“端口到端口”的通信,UDP提供面向事务的简单的不可靠信息传送服务。接下来来看UDP与TCP的区别:UDPTCP......
  • 药品的GMP、GLP、GCP、GAP、GSP、GDP、GPP、GUP
    GMP是GoodManufacturingPractice的简称,即药品生产质量管理规范。检查对象是:①人;②生产环境;③制剂生产的全过程。"人"是实行GMP管理的软件,也是关键管理对象,而"物"是GMP管理的硬件,是必要条件,缺一不可。GMP的三大要素是:①人为产生的错误减小到最低;②防止对医药品的污染和低质量医药......
  • cannot import name '_BindParamClause' from 'sqlalchemy.sql.expression'
    python3.8安装环境组件正常安装运行 flaskdbinit报错 cannotimportname'_BindParamClause'from'sqlalchemy.sql.expression' 问题原因-未知 解决方案更新alembic组件版本pipinstall--upgradealembic 问题解决 ......
  • 2023东莞/成都/深圳产品经理NPDP认证8月19日开班
    产品经理国际资格认证NPDP是新产品开发方面的认证,集理论、方法与实践为一体的全方位的知识体系,为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。  【认证机构】 产品开发与管理协会(PDMA)成立于1979年,是全球范围内产品开发与管理专业人士最杰出的倡导者,协助个人、企业......
  • dpdk编译开发
    下载源码http://core.dpdk.org/download/编译http://core.dpdk.org/doc/quick-start/安装python3安装ninjayuminstallninja-build安装mesonpip3installmeson开始编译tarxfdpdk.tar.gzcddpdkmesonbuildninja-Cbuild确定配置好大页内存mkdir......
  • 斜率优化 dp 学习笔记
    仍然是算导风格的学习笔记例题:[HNOI2008]玩具装箱P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为\(1\cdotsn\)的\(n\)件玩具,第\(i\)件玩具经......
  • 『学习笔记』插入类dp
    概述可以说是一个套路化问题,想出来了就非常好做。前提是你得想出来。转移方程一般也都是特定的:设\(dp_{i,j}\)表示往一个序列里插入了\(i\)个数,这\(i\)个数被分成了\(j\)段的方案数。初始化:\(\begin{cases}dp_{1,i=1}=1\\dp_{1,i\ne1}=0\end{cases}\).......
  • DP vs Non DP
    我们对知识的探究来源于探寻规律,而许多规律性的问题可以分出阶段进行递推解决,这样就形成了DP。DP非常有用,但它并不能取代找规律的过程。即使是多阶段决策问题,发现一些规律可能比直接使用DP更加简单。例子:你有\(n\)个字母A,\(m\)个字母B,你可以将这些字母组成成为一个字......
  • 天翼云加速落地紫金DPU实践应用,让算力供给更高效!
    近日,以“智驱创新·芯动未来”为主题的第三届DPU峰会在北京成功举办。会上,天翼云凭借紫金DPU在架构革新、算力释放、场景落地等多方面的成果,荣膺“2023芯星品牌奖”,技术实力与品牌影响力再获行业认可。天翼云科技有限公司基础架构事业部高/级产品经理雷晓龙在技术生态论坛发表了题......