首页 > 其他分享 >二叉苹果树

二叉苹果树

时间:2024-09-09 21:03:36浏览次数:7  
标签:int long 二叉 add 苹果树 dp

二叉苹果树

题意

给定一棵树,每条边有一个权值。

求留下 \(m\) 条边后与 \(1\) 连通的块内边权和的最大值。

思路

定义 \(dp_{i,j}\) 表示以 \(i\) 为根的子树留下 \(j\) 条边的最大值。

\[dp_{i,j}=\max_{k\in son_i}(dp_{k,t}+dp_{i,j-t-1}+w(i,k)) \]

必选 \((i,k)\) 这条边。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200 + 5;
int tot, ver[N << 1], nxt[N << 1], head[N], edge[N << 1];
int n, m, dp[N][N];
void add(int x, int y, int z) {
	ver[++ tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
	edge[tot] = z;
}
void dfs(int x, int fa) {
	for (int i = head[x], y, z; i; i = nxt[i]) {
		y = ver[i], z = edge[i];
		if (y == fa) continue;
		dfs(y, x);
		for (int j = m; j >= 0; j --) 
			for (int k = 0; k < j; k ++) 
				dp[x][j] = max(dp[x][j], dp[y][k] + dp[x][j - k - 1] + z);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1, u, v, w; i < n; i ++) {
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	dfs(1, 0);
	cout << dp[1][m] << "\n";
	return 0;
}

标签:int,long,二叉,add,苹果树,dp
From: https://www.cnblogs.com/maniubi/p/18405326

相关文章

  • C ++ 从单链表到创建二叉树到二叉树的遍历(结构体)
    首先我们要了解二叉树的数据结构是什么,本质上二叉树是一个有两个节点的链表,我们先了解的单链表的相关定义单链表创建一个朴素的单链表#include<iostream>usingnamespacestd;structNode{intval;Node*next;Node(intx):val(x),next(nullptr){}......
  • 平衡二叉树,二叉树的最大深度
    #include<iostream>#include<vector>#include<queue>#include<cmath>usingnamespacestd;classTreeNode{public: intval; TreeNode*left; TreeNode*right; TreeNode(intvalue):val(value),left(nullptr),right(nullptr){ }}......
  • 二叉树(这节主讲二叉树中的递归)
    目录二叉树的遍历:1.前序遍历:根->左子树->右子树2.中序遍历:左子树->根->右子树3.后序遍历:左子树->右子树->根4.层序遍历:从第一层到最后一层,一层一层地遍历二叉树的基本结构:二叉树中的常用接口:构造一个节点:构建二叉树:二叉树销毁:二叉树节点个数:二叉树叶子节点个数:二......
  • 数据结构--二叉树(C语言实现,超详细!!!)
    文章目录二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码二叉树的概念二叉树(BinaryTree)是数据结构中一种非常重要的树形......
  • DFS算法专题(一)——二叉树中的深搜【回溯与剪枝的初步注入】
    目录1、DFS算法简介2、算法实战应用【leetcode】2.1计算布尔二叉树的值2.1.1算法原理 2.1.2算法代码2.2求根节点到叶节点数字之和  2.2.1算法原理​2.2.2算法代码2.3二叉树剪枝2.3.1算法原理2.3.2算法代码2.4验证二叉搜索树 2.4.1算法原理 2.4.2......
  • 信息学奥赛初赛天天练-84-NOIP2014普及组-基础题3-总线、存储器、邮件协议、二叉树、
    信息学奥赛初赛天天练-84-NOIP2014普及组-基础题3-总线、存储器、邮件协议、二叉树、满二叉树、顶点的度、无向图、有向图PDF文档公众号回复关键字:202409061NOIP2014普及组基础题36CPU、存储器、I/O设备是通过()连接起来的A接口B总线C控制线D系统文......
  • 【数据结构】二叉树的链式结构,二叉树的遍历,求节点个数以及高度
    目录1.二叉树链式结构的概念2.二叉树的遍历2.1前序遍历2.2中序遍历2.3后序遍历2.4层序遍历3.二叉树的节点个数以及高度3.1二叉树节点个数3.2 二叉树叶子节点个数3.3二叉树的高度3.4 二叉树第k层节点个数3.5 二叉树查找值为x的节点4. 二叉树的创建和......
  • 动态规划:不同二叉搜索树
    前言        动态规划在树的应用中是一种非常重要的算法技术,主要用于解决树结构上的优化问题。树形动态规划(TreeDynamicProgramming,简称树形DP)通常涉及在树结构上进行状态转移,以求解最优值问题。以下是对树形动态规划的详细解释和应用场景的总结:**基本概念**: ......
  • LeeCode-226. 翻转二叉树
    要求给你一棵二叉树的根节点root,翻转这棵二叉树,并返回其根节点。如下图所示反转所有左右节点.解题思路与94题类似,采用递归调用遍历子节点。在基本结构中,先调换左右节点,再对左右节点内部递归调用本身。实现代码TreeNode*invertTree(TreeNode*root){if......
  • 完全二叉树与堆
    目录认识堆的简单结构:二叉树:完全二叉树:堆:大堆:小堆:完全二叉树可以由顺序表实现:堆的常用接口(我们实现一个大堆):方便交换的函数:堆的初始化:堆的销毁:堆插入:堆顶数据的删除:取堆顶数据:堆的判空:向上调整:向下调整:认识堆的简单结构:二叉树:二叉树是一种每个节点最多......