首页 > 其他分享 >luoguP1122 最大子树和

luoguP1122 最大子树和

时间:2024-11-03 15:20:18浏览次数:4  
标签:std 子树 最大 luoguP1122 dfs int adj 节点 dp

有一棵N个节点的树,节点i的权值为w[i],可以剪掉其中一些枝,使得剩下的树上节点权值之和最大,求最大值。
1<=N<=16000; -1E6<=w[i]<=1E6

分析:题目要求至少要选1个节点,设dp[i]表示以i为根的子树,并且选择i的最大权值和。对于i的每个子节点,可以选或不选。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
	int n;
	std::cin >> n;
	std::vector<i64> w(n);
	for (int i = 0; i < n; i++) {
		std::cin >> w[i];
	}
	std::vector<std::vector<int>> adj(n);
	for (int i = 1; i < n; i++) {
		int x, y;
		std::cin >> x >> y;
		x--, y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	std::vector<i64> dp(n);

	auto dfs = [&](auto self, int x, int p) -> void {
		dp[x] = w[x];
		for (auto i : adj[x]) if (i != p) {
			self(self, i, x);
			dp[x] += std::max(0LL, dp[i]);
		}
	};

	dfs(dfs, 0, 0);

	std::cout << *std::max_element(dp.begin(), dp.end()) << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	while (t--) solve();
	return 0;
}

标签:std,子树,最大,luoguP1122,dfs,int,adj,节点,dp
From: https://www.cnblogs.com/chenfy27/p/18523482

相关文章

  • LeetCode 3165.不包含相邻元素的子序列的最大和:单点修改的线段树(动态规划)
    【LetMeFly】3165.不包含相邻元素的子序列的最大和:单点修改的线段树(动态规划)力扣题目链接:https://leetcode.cn/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/给你一个整数数组nums和一个二维数组queries,其中queries[i]=[posi,xi]。对于每个查......
  • 字节青训-寻找最大葫芦
    问题描述在一场经典的德州扑克游戏中,有一种牌型叫做“葫芦”。“葫芦”由五张牌组成,其中包括三张相同牌面值的牌 aa 和另外两张相同牌面值的牌 bb。如果两个人同时拥有“葫芦”,我们会优先比较牌 aa 的大小,若牌 aa 相同则再比较牌 bb 的大小。在这个问题中,我们对“......
  • 岛屿的最大面积(深搜
    卡码网 100.岛屿的最大面积题目描述给定一个由 1(陆地)和0(水)组成的矩阵,计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成,并且四周都是水域。你可以假设矩阵外均被水包围。输入描述第一行包含两个整数N,M......
  • 滑动窗口最大值
    滑动窗口最大值题目链接:LeetCode239描述给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例输入:nums=[1,3,-1,-3,5,3,6,7],k=3......
  • RabbitMQ实现轮询形式消息最大发送失败次数,及详细解析
    RabbitMQ设置消息最大发送失败次数,达到三次后不确认消息(此处根据业务需求可考虑使不确认的消息进入死信交换机)配置文件:spring:rabbitmq:host:192.168.1.248port:5672username:adminpassword:123456virtual-host:powernodepublisher......
  • LeetCode100之滑动窗口最大值(239)--Java
    1.问题描述        给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。        示例1输入:nums=[1,3,-1,-3,5,3,6......
  • LeetCode题练习与总结:矩形区域不超过 K 的最大数值和--363
    一、题目描述给你一个 mxn 的矩阵 matrix 和一个整数 k ,找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。题目数据保证总会存在一个数值和不超过 k 的矩形区域。示例1:输入:matrix=[[1,0,1],[0,-2,3]],k=2输出:2解释:蓝色边框圈出来的矩形区域 [[......
  • 超级饮料的最大强化能量
    超级饮料的最大强化能量题目来自未来的体育科学家给你两个整数数组energyDrinkA和energyDrinkB,数组长度都等于n。这两个数组分别代表A、B两种不同能量饮料每小时所能提供的强化能量。你需要每小时饮用一种能量饮料来最大化你的总强化能量。然而,如果从一种能量饮料切换......
  • 最大子矩阵和
    最大子矩阵和题目Leetcode:面试题17.24.最大子矩阵给定一个正整数、负整数和0组成的N×M矩阵,编写代码找出元素总和最大的子矩阵。返回一个数组[r1,c1,r2,c2],其中r1,c1分别代表子矩阵左上角的行号和列号,r2,c2分别代表右下角的行号和列号。若有多个满足条件的......
  • 2024-11-1-leetcode每日一题-3259. 超级饮料的最大强化能量
    题目描述来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB,数组长度都等于 n。这两个数组分别代表A、B两种不同能量饮料每小时所能提供的强化能量。你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而,如果从一种能量饮料切换到另一种,你......