「BZOJ3252」攻略
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
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
|
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; } |
计数器 9854456
OI 课件=>
OI 课件=>
[…] Orz hzwer […]