0000

用户名：dafei0710

访问量：5712

签　名：

等　　级
排　　名	2484
经　　验	2285
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校	湖北汽车工业学院
专　　业

　　自我简介：

TA的其他文章

[编程入门]数字的处理与判断-题解(C语言代码)
浏览：65

[STL训练]sort练习-题解(C++代码)
浏览：1070

蓝桥杯2015年第六届真题-垒骰子-题解(C++代码)
浏览：784

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

蓝桥杯2015年第六届真题-生命之树（C++代码）

　　作者: 0000　　　　发表时间：2020-03-11 15:17:43 浏览：508　|　评论：1　

原题链接：蓝桥杯2015年第六届真题-生命之树

「算法描述」
首先我们可以枚举每个点是否在 S 中，只需要判断 S 是否是一个连通块就可以了。时间复杂度 O(n 2^n) 期望得分 30 分。
我们把这棵无根树定一个根，将其转为有根树。这样每个点就有了深度。
令 f_v 表示如果 v 一定在点集 S 中，且 S 中的所有点均在 v 这棵子树中时，S 的权值和的最大值。
考虑 v 的各个孩子所代表的子树。令 u 为 v 的一个孩子。
1. 若 S 中含有子树 u 内的点，则 u 一定也在 S 中，此时 S 中所有在 u 这棵子树内的权值和的最大值为 f_u ，即 u 这棵子树给 v 贡献的值为 f_u；
2. 若 S 中不含有子树 u 内的点，则 u 这棵子树给 v 贡献的权值为 0 。
所以我们可以推出 f_v 的表达式： f_v = w_v + sum_{u 是 v 的孩子} max(f_u, 0) 其中 w_v 表示 v 的权值。
利用这个表达式，我们可以求出所有的 f ，在其中选一个最大值就是最优解。

```cpp
 #include <cstdio>
 #include <vector>
using namespace std;

const int N = 1e5 + 10;

vector<int> G[N];
long long w[N], ans;

void dfs(int u, int fa) {
    for (int e = 0; e < (int)G[u].size(); ++e) {
        int v = G[u][e];
        if (v != fa) {
            dfs(v, u);
            w[u] += max(w[v], 0ll);
        }
    }
    if (ans < w[u]) ans = w[u];
}

int main() {
//    freopen("mcp.in" , "r", stdin );
//    freopen("mcp.out", "w", stdout);

int n;
    scanf("%d", &n);
    for (int i = 1, a; i <= n; ++i)
        scanf("%d", &a), w[i] = a;
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

dfs(1, 0);
    printf("%lld\n", ans);
    return 0;
}
```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

哎哟那个嘿

当所有点权值都是负数时，是不是就错了

2020-08-16 14:52:06

0000

TA的其他文章

你可能喜欢

分糖果（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C二级辅导-求偶数和（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

蓝桥杯2015年第六届真题-生命之树（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言训练-尼科彻斯定理（C语言代码）

【计算直线的交点数】（C语言代码）

1124题解

核桃的数量（C语言代码）

剪刀石头布（C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

0000

TA的其他文章

你可能喜欢

分糖果 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）

C二级辅导-求偶数和 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

蓝桥杯2015年第六届真题-生命之树 （C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言训练-尼科彻斯定理 （C语言代码）

【计算直线的交点数】 （C语言代码）

1124题解

核桃的数量 （C语言代码）

剪刀石头布 （C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

分糖果（C语言代码）

C二级辅导-求偶数和（C语言代码）

蓝桥杯2015年第六届真题-生命之树（C++代码）

　　评论区

C语言训练-尼科彻斯定理（C语言代码）

【计算直线的交点数】（C语言代码）

核桃的数量（C语言代码）

剪刀石头布（C++代码）