【bzoj3252】攻略 贪心+DFS序+线段树
2024-09-07 04:07:55
题目描述
题目简述:树版[k取方格数]
众所周知,桂木桂马是攻略之神,开启攻略之神模式后,他可以同时攻略k部游戏。
今天他得到了一款新游戏《XX半岛》,这款游戏有n个场景(scene),某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构:开始游戏时在根节点(共通线),叶子节点为结局。每个场景有一个价值,现在桂马开启攻略之神模式,同时攻略k次该游戏,问他观赏到的场景的价值和最大是多少(同一场景观看多次是不能重复得到价值的)
“为什么你还没玩就知道每个场景的价值呢?”
“我已经看到结局了。”
输入
第一行两个正整数n,k
第二行n个正整数,表示每个场景的价值
以下n-1行,每行2个整数a,b,表示a场景有个选择支通向b场景(即a是b的父亲)
保证场景1为根节点
输出
输出一个整数表示答案
样例输入
5 2
4 3 2 1 1
1 2
1 5
2 3
2 4
样例输出
10
题解
贪心+DFS序+树状数组
首先有个显而易见的贪心策略:每次选能够获得最大价值的点。
于是我们只需要设法维护这个贪心即可。
考虑到一个点被使用,影响到的只有它的子树中的节点。所以我们可以按路径长度对DFS序上每个点建立线段树,并线段树维护DFS序上的区间最大值、区间最大值位置,支持修改操作。
所以我们每次操作拿出最大值加到答案中,并对于最大值位置对应的点,在它到根节点的路径上不断向上移动,每到一个点就更新它的子树,把它们的价值减去这个点的权值。直到移动到某个已经被使用了的点停止。(因为如果一个点被使用,则它的祖先节点也一定均被使用)。
时间复杂度为$O((n+k)\log n)$。
#include <cstdio>
#include <algorithm>
#define N 200010
#define lson l , mid , x << 1
#define rson mid + 1 , r , x << 1 | 1
using namespace std;
typedef long long ll;
int fa[N] , head[N] , to[N] , next[N] , cnt , pos[N] , ref[N] , last[N] , tot , mp[N << 2] , del[N];
ll w[N] , v[N] , mx[N << 2] , tag[N << 2];
void add(int x , int y)
{
to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;
}
void dfs(int x)
{
int i;
v[x] = v[fa[x]] + w[x] , pos[x] = ++tot , ref[tot] = x;
for(i = head[x] ; i ; i = next[i]) dfs(to[i]);
last[x] = tot;
}
void pushup(int x)
{
int l = x << 1 , r = x << 1 | 1;
if(mx[l] > mx[r]) mx[x] = mx[l] , mp[x] = mp[l];
else mx[x] = mx[r] , mp[x] = mp[r];
}
void pushdown(int x)
{
if(tag[x])
{
int l = x << 1 , r = x << 1 | 1;
mx[l] -= tag[x] , mx[r] -= tag[x];
tag[l] += tag[x] , tag[r] += tag[x];
tag[x] = 0;
}
}
void build(int l , int r , int x)
{
if(l == r)
{
mx[x] = v[ref[l]] , mp[x] = l;
return;
}
int mid = (l + r) >> 1;
build(lson) , build(rson);
pushup(x);
}
void update(int b , int e , ll a , int l , int r , int x)
{
if(b <= l && r <= e)
{
mx[x] -= a , tag[x] += a;
return;
}
pushdown(x);
int mid = (l + r) >> 1;
if(b <= mid) update(b , e , a , lson);
if(e > mid) update(b , e , a , rson);
pushup(x);
}
int main()
{
int n , k , i , x , y;
ll ans = 0;
scanf("%d%d" , &n , &k);
for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &w[i]);
for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , fa[y] = x , add(x , y);
dfs(1);
build(1 , n , 1);
while(k -- )
{
ans += mx[1] , x = ref[mp[1]];
while(x && !del[x]) update(pos[x] , last[x] , w[x] , 1 , n , 1) , del[x] = 1 , x = fa[x];
}
printf("%lld\n" , ans);
return 0;
}
最新文章
- javascript keycode大全
- [开源 .NET 跨平台 数据采集 爬虫框架: DotnetSpider] [二] 基本使用
- 20145227&;20145201 《信息安全系统设计基础》实验五
- C# 模拟提交 Form表单的数据
- iOS-协议与代理<;转>;
- Django 使用原生SQL
- C# 运算符 if
- 用jQuery写了一个模态框插件
- C#快速入门
- 一个简单的迷你jQuery实现
- Fullcalendar改版后发布到IIS或者tomcat里面前端加载数据不显示的问题
- 支付宝2018年最新SDK对接验签的问题
- day15-ajax和jquery
- c++11 stl 学习之 shared_ptr
- Unity----Scene加载问题
- 1067 - Combinations---LightOj(Lucas求组合数)
- Java-单向链表算法
- 微软IE团队发布《逃离XP》浏览器小游戏
- SQL存储过程将符合条件的大量记录批量删除脚本
- webform获取微信用户的授权
热门文章
- 使用ABAP批量下载有道云笔记中的图片
- 使用tensorflow object_detection API训练自己的数据遇到的问题及解决方法
- UVA 12905 Volume of Revolution (几何,微积分)
- VS开发软winform软件的更改用户使用权限
- 2018.4.1 Ubuntu16.04 下配置Tomcat服务器以及设置dingshi启动
- python_87_shelve模块
- Google 出品的 Java 编码规范,强烈推荐,权威又科学!
- 最大长度回文子串(Manacher&#39;s algorithm)
- mysql中添加数据时,报错(incorrect string value:&#39;\xf0\x9f ) 字符转换不正确
- postman测试传入json