首页 > 其他分享 >康复训练の树形DP

康复训练の树形DP

时间:2023-04-11 19:11:37浏览次数:38  
标签:now int 树形 DP 康复训练 Nw Nt dp define

所有代码的开头头文件,宏定义和命名空间如下

#include <bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define ll long long
#define CI const int
#define RI int
#define W while
#define gc getchar
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define Mt(a,x) memset((a),(x),sizeof(a))
using namespace std;
namespace SlowIO {
	void Readc (char& c) {W (isspace (c = gc ()));}
	Tp void Read (Ty& x) {char c; int f = 1; x = 0; W (! isdigit (c = gc ())) f = c ^ '-' ? 1 : -1; W (x = (x * 10) + (c ^ 48), isdigit (c = gc ())); x *= f;}
	Ts void Read (Ty& x, Ar&... y) {Read (x); Read (y...);}
} using namespace SlowIO;

P1122 最大子树和

solution

不妨设此无根树的根为 1, 父亲为 0。设 \(dp_i\) 表示以 \(i\) 为根的子树中权值和最大的子树的权值和。

明显的,对于 \(now\) 的一个儿子 \(s\),如果 \(dp_s\le 0\),则不选此子树,否则选择。

转移方程式:\(dp_{now}=\sum\limits_{s\in now}[dp_s>0]dp_s\)。答案为所有 \(dp_i\) 中最大的一个。

PS:记得邻接表大小开两倍。

code

CI N = 3.2e4; int n, D[N + 5];
namespace graph {
	int H[N + 5], Nt[N + 5], T[N + 5], C = 0;
	void A (int u, int v) {++ C; T[C] = v; Nt[C] = H[u]; H[u] = C;}
} using namespace graph;
void Do (int Nw, int F) {RI i, j; for (i = H[Nw]; i; i = Nt[i]) {if (T[i] == F) continue; Do (T[i], Nw); if (D[T[i]] > 0) D[Nw] += D[T[i]];}}
int main () {
	RI i, j; for (Read (n), i = 1; i <= n; ++ i) Read (D[i]); for (i = 2; i <= n; ++ i) {int u, v; Read (u, v); A (u, v); A (v, u);} Do (1, 0);
	return printf ("%d\n", *max_element (D + 1, D + n + 1)), 0;
}

标签:now,int,树形,DP,康复训练,Nw,Nt,dp,define
From: https://www.cnblogs.com/ClapEcho233/p/17307309.html

相关文章

  • 微信小程序开发——getLocation:fail the api need to be declared in the requiredPr
    getLocation:failtheapineedtobedeclaredintherequiredPrivateInfosfieldinapp.json/ext.json异常解析:app.json中没配置requiredPrivateInfos参数,按下边示例代码配置即可。示例代码:{..."permission":{"scope.userLocation":{"desc&qu......
  • el-table树形数据与懒加载
    <template><divclass="page"><divclass="page-box"><h3style="margin-top:0">类目/榜单管理</h3><el-inputplaceholder="请输入关键字"v-model="keyWord"style="......
  • Java中创建线程的方式以及线程池创建的方式、推荐使用ThreadPoolExecutor以及示例
    场景Java中创建线程的方式有三种1、通过继承Thread类来创建线程定义一个线程类使其继承Thread类,并重写其中的run方法,run方法内部就是线程要完成的任务,因此run方法也被称为执行体,使用start方法来启动线程。2、通过实现Runanle接口来创建线程首先定义Runnable接口,并重写Runnab......
  • oracle导出impdp导入已存在表设置TABLE_EXISTS_ACTION参数
    目录oracle导出impdp导入已存在表设置TABLE_EXISTS_ACTION参数1、TABLE_EXISTS_ACTION参数说明2、使用示例oracle导出impdp导入已存在表设置TABLE_EXISTS_ACTION参数1、TABLE_EXISTS_ACTION参数说明有四个参数:skip:默认操作,跳过已存在的表不做处理。append:在原有的数据上追加......
  • 405 最长公共子序列 线性DP
    视频链接:https://www.bilibili.com/video/BV1EK411K7Eb/ #include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=1010;intn,m;chara[N],b[N];intf[N][N];intmain(){cin>>n>>m>>......
  • 402 数字三角形 线性DP
    视频链接:LuoguP1216[USACO1.5][IOI1994]数字三角形NumberTriangles#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=1005;intn,f[N][N];intmain(){scanf("%d",&n);for(inti=1;i......
  • Leetcode(剑指offer专项训练)——DP专项(8)
    最长递增路径题目给定一个 mxn整数矩阵 matrix,找出其中最长递增路径的长度。对于每个单元格,你可以往上,下,左,右四个方向移动。不能在对角线方向上移动或移动到边界外(即不允许环绕)。链接DP但是依旧不能覆盖所有的情况classSolution{public:intlongest......
  • 换根dp
    给定一棵树,树中包含nn个结点(编号11~nn)和n−1n−1条无向边,每条边都有一个权值。请你在树中找到一个点,使得该点到树中其他结点的最远距离最近。输入格式第一行包含整数nn。接下来n−1n−1行,每行包含三个整数ai,bi,ciai,bi,ci,表示点aiai和bibi之间存在一条权值为ci......
  • 「学习笔记」数位 DP
    「学习笔记」数位DP意义不大的题不写了。点击查看目录目录「学习笔记」数位DP概述例题P2657[SCOI2009]windy数思路代码P4317花神的数论题思路P4124[CQOI2016]手机号码思路代码haha数题意思路代码0和1的熟练题意思路代码苍与红的试炼题意思路代码概述数位DP一般......
  • 算法-递归三(树形结构)
    publicclassSolution{publicIList<IList<int>>Permute(int[]nums){varrtItem=newList<int>();varvisited=newDictionary<int,bool>();IList<IList<int>>rt=newList<IList<int&......