Happy Tree Friends（图论）

　

happy tree friend

题目描述

There is a HAPPy Tree on an island. Happy Tree consists of n apples linked by n-1 branches and the No.1 apple is the root of the tree. Each apple has a value a_i.

Today, k friends are playing under Happy Tree. Each of them can select only one apple, then gets the sum of the values from root to the selected apple, and take all the apples on the road (including the root and the selected apple). Of course, an apple can only be taken once.

Now, they want to know the maximum value they can get. They promise that everyone can select at least one apple.

输入

The first line consists of two non-negative integers, the number of apples n, and the number of friends k. ( 1 ≤ n ,k ≤2×105 )

The second line consists of n non-negative integers, the value of the i-th apple a_i. ( 1 ≤ a_i ≤ 109 )

Then there are n-1 lines, each line consists of two non-negative integers, and describe a branch between u and v. ( 1≤u ,v ≤n )

输出

Only one integer, the maximum value they can get.

样例输入

5 2

4 3 2 1 1

1 2

1 5

2 3

2 4

样例输出

10

思路

如图所示将树中每条较大链取出，放入优先队列中，前k条链的总和即为答案

代码实现

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int N=2e5+10;
 
struct  node
{
    int to,nxt;
}G[N<<1];
int n,k,cnt;
int head[N<<1];
ll a[N];
priority_queue<ll>que;
 
void add(int u,int v)
{
    G[++cnt].to=v;
    G[cnt].nxt=head[u];
    head[u]=cnt;
}
 
ll dfs(int x,int bf)
{
    ll maxs=0;
    for(int i=head[x];i;i=G[i].nxt)
    {
        int v=G[i].to;
        if(v==bf) continue;
        ll temp=dfs(v,x);
        if(temp>maxs)
        {
            que.push(maxs);
            maxs=temp;
        }
        else que.push(temp);
    }
    return maxs+a[x];
}
 
 
 
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    ll ans=dfs(1,-1);
    k--;
    while(k-- && que.size())
    {
        ans+=que.top();
        que.pop();
    }
    printf("%lld\n",ans);
    return 0;
}

文章最后发布于: 2019-09-06 14:08:26

相关阅读

如何不花钱搞定1000个铁杆用户？

小编导读 : 2015年，金错刀频道会启动一个创业公益项目——《创业狠问答》。第一季就是“不花钱”系列。我被很多创业者问的最多的

论-100000乘以-100000

论-100000乘以-100000 #我真是闲的无聊，菜的一批，才会去论-10000乘以-100000，但我不知道为什么会爆？#计算完成之后类型转换#计算完成

北京监狱开通支付宝扫码存款：每次最多只能存1000元

A5创业网（公众号：iadmin5）1月15日报道，近日北京监狱与支付宝合作，上线了服刑人员综合账务管理系统，为服刑人员提供了狱内支付、家属存款

如何让营销QQ每天1000次邀请不受限制加好友？

营销QQ是拥有10万好友容量的一个企业版QQ，可以每天发出1000次好友邀请，但是很多用户在购买使用之后，发现并不能达到1000次邀请量，经常

浅谈setInterval(aa,1000)与setInterval(aa(),1000)的

一直有个疑惑，在定时器上调用某个方法时，加括号和不加括号有什么区别。今天做了个实验，发现，不加括号定时器会每秒执行一次，加了括号只