zss192

用户名：zss192

访问量：959

签　名：

等　　级
排　　名	13902
经　　验	905
参赛次数	0
文章发表	9
年　　龄	0
在职情况	学生
学　　校	河南大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯基础练习VIP-字符串对比（简洁版）
浏览：66

蓝桥杯基础练习VIP-完美的代价
浏览：128

蓝桥杯基础练习VIP-报时助手
浏览：146

你可能喜欢

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

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

蓝桥杯2015年第六届真题-生命之树

　　作者: zss192　　　　发表时间：2021-04-09 17:12:36 浏览：199　|　评论：0　

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

#include <iostream>
    #include <vector>
    using namespace std;
    typedef long long ll;
    const int N = 100010;
    
    int n;
    ll quan[N];    //初始输入存放每个点的权值，后续存放以每个节点为根节点时的连通最大权值和
    vector<int> linjie[N];   //邻接表
    ll res;
    
    //以root为根算出最大权值和
    void dfs(int root, int father){
        for (int i = 0; i < linjie[root].size(); i++)
        {
            int son = linjie[root][i];
            if (son != father)  //判断邻接表中的son节点是不是已经计算过了
            {//如dfs(a,0)进来调用dfs(b,a)时，son=a,而此时son=father=a说明就是从a过来的，已经计算过a了
                dfs(son, root);
                if (quan[son] > 0)  //如果子节点的权值大于0则将子节点的权值加到root节点的权值上
                    quan[root] += quan[son];
            }
        }
        res = max(res, quan[root]); //从所有以每个节点为根节点的最大权值和中取最大值
    }
    int main(){
        cin>>n;
    
        for (int i = 1; i <= n; i ++ ) 
            cin>>quan[i];
        
        for (int i = 1; i < n ; i ++ )  //构造邻接表
        {
            int u, v;
            cin>>u>>v;
            linjie[u].push_back(v); 
            linjie[v].push_back(u);
        }
        
        dfs(1,0);
        cout<<res<<endl;
        
        return 0;
    }

0.0分

1 人评分

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

zss192

TA的其他文章

你可能喜欢

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

上车人数（C语言代码）

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

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

蓝桥杯2015年第六届真题-生命之树

评论区

精彩推荐

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

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

【亲和数】（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

C语言训练-大、小写问题（C语言代码）

简单的a+b （C语言代码）

【矩阵】（C++代码）

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

zss192

TA的其他文章

你可能喜欢

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

上车人数 （C语言代码）

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

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

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

蓝桥杯2015年第六届真题-生命之树

评论区

精彩推荐

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

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

【亲和数】 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

C语言训练-大、小写问题 （C语言代码）

简单的a+b （C语言代码）

【矩阵】 （C++代码）

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

上车人数（C语言代码）

　　评论区

【亲和数】（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

C语言训练-大、小写问题（C语言代码）

【矩阵】（C++代码）