蓝桥杯每日一题2023.12.4

电玩女神 2024-02-05 11:41 53阅读 0赞

### 题目描述 ###

[竞赛中心 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn]

![67336169fe0e4e169f7a96e1300e87ec.png][]

### 题目分析 ###

本题使用树型DP，蓝桥杯官网出现了一个点的错误，但实际答案是正确的

**状态表示：f\[u\]：在以u为根的子树中包含u的所有联通块的权值的最大值**

假设s1，s2,…sk 是u的孩子

**f\[u\]=w\[u\]+max(f\[s1\],0)+max(f\[s2\],0)+…max(f\[sk\],0)**

从根结点开始深度优先遍历每个子结点

最后遍历每一个点的权值，找出最大的点即可

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e5 + 10, M = 2 * N;
    int n, a, b, w[N], e[M], ne[M], h[N], idx;
    ll f[N]; 
    void add(int a, int b)
    {
    	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
    }
    void dfs(int u, int father)//存当前节点，当前节点的父亲节点（防止往回搜索） 
    {
    	f[u] = w[u];
    	for(int i = h[u]; i != -1; i = ne[i])//寻找u所有的儿子 
    	{
    		int j = e[i];
    		if(j != father)//如果j不是往回搜的 
    		{
    			dfs(j, u);//继续向下搜索 
    			f[u] += max(0ll, f[j]);
    		}
    	}
    }
    int main()
    {
    	cin >> n;
    	memset(h, -1, sizeof h); 
    	for(int i = 1; i <= n; i ++)cin >> w[i];
    	for(int i = 1; i < n; i ++)
    	{
    		cin >> a >> b;
    		add(a, b);
    		add(b, a);
    	}
    	dfs(1, -1); 
    	ll res = f[1];
    	for(int i = 2; i <= n; i ++)
    	{
    		res = max(res, f[i]);
    	}
    	cout << res;
    	return 0;	
    }

[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/131/learning/?page=1&first_category_id=1&name=%E7%94%9F%E5%91%BD
[67336169fe0e4e169f7a96e1300e87ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/02816725cccd4263be262295071bf60b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，53人围观）

还没有评论，来说两句吧...

相关阅读

相关日志统计(蓝桥杯每日一题)

日志统计(蓝桥杯每日一题) 小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。其中每一行的格式是： ts id 表示在 ts 时

柔情只为你懂/ 2024年03月26日 13:13/ 0 赞/ 109 阅读

相关字符串删减(蓝桥杯每日一题)

字符串删减给定一个由 n个小写字母构成的字符串。现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。请问，最少需要删掉多少个字母？如果

小咪咪/ 2024年03月26日 13:10/ 0 赞/ 84 阅读

相关 K倍区间（蓝桥杯每日一题）

K倍区间（蓝桥杯每日一题）给定一个长度为 N的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj之和是 K的倍数，我们就称这个区间 \[i,j\

ゞ浴缸里的玫瑰/ 2024年03月26日 12:48/ 0 赞/ 95 阅读

相关截断数组（蓝桥杯每日一题）

截断数组（蓝桥杯每日一题）给定一个长度为 n的数组 a1,a2,…,an。现在，要将该数组从中间截断，得到三个非空子数组。要求，三个子数组内各元素之和都相等。

淡淡的烟草味﹌/ 2024年03月26日 12:32/ 0 赞/ 72 阅读

相关蓝桥杯每日一题2023.9.14

[蓝桥杯2022年第十三届省赛真题-刷题统计 - C语言网 (dotcpp.com)][2022_-_ - C_ _dotcpp.com] 题目描述小明决定从下周一开

桃扇骨/ 2024年03月03日 08:34/ 0 赞/ 44 阅读

相关蓝桥杯每日一题2023.9.19

[蓝桥杯2021年第十二届省赛真题-砝码称重 - C语言网 (dotcpp.com)][2021_-_ - C_ _dotcpp.com] 题目描述你有一架天平和 N

╰半橙微兮°/ 2024年03月02日 04:12/ 0 赞/ 40 阅读

相关蓝桥杯每日一题2023.11.1

题目描述 [乘积最大 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn] ![c1c6e3cc17d14178891f494157e080bb.

约定不等于承诺〃/ 2024年02月20日 11:37/ 0 赞/ 58 阅读

相关蓝桥杯每日一题2023.11.10

[“蓝桥杯”练习系统 (lanqiao.cn)][_lanqiao.cn] 题目描述 ![4032d278933e4bbfa1ac925056ff3d5a.png][]

淡淡的烟草味﹌/ 2024年02月19日 11:40/ 0 赞/ 86 阅读

相关蓝桥杯每日一题2023.11.24

题目描述 ![74f53029c5b2425ebba5149b74392ac4.png][] include <stdio.h> define N 10

桃扇骨/ 2024年02月17日 09:57/ 0 赞/ 61 阅读

相关蓝桥杯每日一题2023.11.22

题目描述 ![9fe1856dc34b47d7933b1e56fda879be.png][] 题目分析由题目知其每个品牌积分一定小于315故直接暴力枚举每个品牌

妖狐艹你老母/ 2024年02月17日 09:08/ 0 赞/ 54 阅读