Description

题目简述：树版[k取方格数]
众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。
今天他得到了一款新游戏《XX半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观看多次是不能重复得到价值的）
“为什么你还没玩就知道每个场景的价值呢？”
“我已经看到结局了。”

Input

第一行两个正整数n,k
第二行n个正整数，表示每个场景的价值
以下n-1行,每行2个整数a,b，表示a场景有个选择支通向b场景（即a是b的父亲）
保证场景1为根节点

Output

输出一个整数表示答案

Sample Input

5 2
4 3 2 1 1
1 2
1 5
2 3
2 4

Sample Output

10

HINT

对于100%的数据，n<=200000，1<=场景价值<=2^31-1

题解

首先显然每次取最大权和的链

bzoj上标签贴的是dfs序+线段树。。。

每次从底端选个最大权和点，将它到根的链取走，对于链上的每个点x，要将x子树内的叶节点的权值和减去x的权值，因为下次取x子树的叶节点不能再次得到x的权值，用dfs+线段树就可以实现每次找叶节点最大值，以及修改子树权值

我写的是另一种做法

发现每次一定是选取一个点，将它子树内权值和最大的链取走，以后就不会再选取链上的点

那么用堆维护这一过程，取最大值，删去链的所有点

复杂度都为nlogn

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<ext/pb_ds/priority_queue.hpp>
#define pa pair<ll,int>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n,K,cnt;
int v[200005],last[200005];
ll mx[200005];
__gnu_pbds::priority_queue<pa >::point_iterator id[200005];
struct edge{int to,next;}e[200005];
__gnu_pbds::priority_queue<pa >q;
void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void dp(int x)
{
    for(int i=last[x];i;i=e[i].next)
{
dp(e[i].to);
mx[x]=max(mx[x],mx[e[i].to]);
}
mx[x]+=v[x];
id[x]=q.push(make_pair(mx[x],x));
}
void del(int x)
{
q.erase(id[x]);
for(int i=last[x];i;i=e[i].next)
if(mx[e[i].to]==mx[x]-v[x])
{
del(e[i].to);
break;
}
}
int main()
{
n=read();K=read();
for(int i=1;i<=n;i++)v[i]=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
insert(u,v);
}
dp(1);
for(int i=1;i<=K&&!q.empty();i++)
{
int x=q.top().second;
ans+=mx[x];
del(x);
}
printf("%lld\n",ans);
return 0;
}