bzoj 3252 攻略长链剖分思想+贪心

攻略

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 889 Solved: 423
[Submit][Status][Discuss]

Description

题目简述：树版[k取方格数]

众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。今天他得到了一款新游戏《XX

半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状

结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同

时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观看多次是不能重复得到价值的）

“为什么你还没玩就知道每个场景的价值呢？”

“我已经看到结局了。”

Input

第一行两个正整数n,k

第二行n个正整数，表示每个场景的价值

以下n-1行,每行2个整数a,b，表示a场景有个选择支通向b场景（即a是b的父亲）

保证场景1为根节点

n<=200000，1<=场景价值<=2^31-1

Output

输出一个整数表示答案

Sample Input

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

Sample Output

其实有种比较好的算法，就是长链剖分放入队列，排个序就可以了。

然而配对堆实现了一下，比较麻烦，删除的东西比较多，但是复杂度是一的。

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