BZOJ_3252_攻略_线段树+dfs序

时间:2022-09-06 15:00:44

BZOJ_3252_攻略_线段树+dfs序

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

10

k取方格数有一个经典的网络流做法。
由于网络流是基于贪心来找最长的一条路来增广的的,所以放到树上就转化为了k次查询根到叶子路径点权和最大的叶子编号。
然后把路径上点的贡献减去。
由于每个点最多删一次,可以每次暴力向上走,一次修改一条链的贡献。
可以把叶子的dfs序搞出来,每次修改就对应一段区间修改。
线段树维护区间最值即可。
 
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 200050
#define ls p<<1
#define rs p<<1|1
typedef long long ll;
int mx[N<<2];
ll t[N<<2],inc[N<<2],ans;
int head[N],to[N<<1],nxt[N<<1],val[N],cnt,kill[N],dfn[N],son[N],k,tot,fa[N],turn[N],n;
ll dis[N],dd[N];
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
void dfs(int x,int y) {
dis[x]=dis[y]+val[x];
int i,flg=0; fa[x]=y;
dfn[x]=tot+1;
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) flg=1;
}
if(!flg) {
dfn[x]=son[x]=++tot;
turn[tot]=x;
return ;
}
dfn[x]=tot+1;
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
dfs(to[i],x);
}
}
son[x]=tot;
}
void pushup(int p) {
if(t[ls]>t[rs]) mx[p]=mx[ls],t[p]=t[ls];
else mx[p]=mx[rs],t[p]=t[rs];
}
void build(int l,int r,int p) {
if(l==r) {
mx[p]=turn[l];
t[p]=dis[turn[l]];
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls); build(mid+1,r,rs);
pushup(p);
}
void pushdown(int p) {
ll d=inc[p];
if(d) {
t[ls]+=d; t[rs]+=d;
inc[ls]+=d; inc[rs]+=d;
inc[p]=0;
}
}
void update(int l,int r,int x,int y,int v,int p) {
if(x<=l&y>=r) {
t[p]+=v; inc[p]+=v; return ;
}
pushdown(p);
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,y,v,ls);
if(y>mid) update(mid+1,r,x,y,v,rs);
pushup(p);
}
void solve(int x) {
if(kill[x]||!x) return ;
kill[x]=1;
update(1,tot,dfn[x],son[x],-val[x],1);
solve(fa[x]);
}
int main() {
scanf("%d%d",&n,&k);
int i,x,y;
for(i=1;i<=n;i++) {
scanf("%d",&val[i]);
}
for(i=1;i<n;i++) {
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
build(1,tot,1);
for(i=1;i<=k;i++) {
ans+=t[1];
solve(mx[1]);
}
printf("%lld\n",ans);
}

BZOJ_3252_攻略_线段树+dfs序的更多相关文章

  1. Tsinsen A1505&period; 树(张闻涛) 倍增LCA&comma;可持久化线段树&comma;DFS序

    题目:http://www.tsinsen.com/A1505 A1505. 树(张闻涛) 时间限制:1.0s   内存限制:512.0MB    总提交次数:196   AC次数:65   平均分: ...

  2. 【XSY2534】【BZOJ4817】树点涂色 LCT 倍增 线段树 dfs序

    题目大意 ​ Bob有一棵\(n\)个点的有根树,其中\(1\)号点是根节点.Bob在每个点上涂了颜色,并且每个点上的颜色不同.定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜 ...

  3. 【bzoj4817】树点涂色 LCT&plus;线段树&plus;dfs序

    Description Bob有一棵n个点的有根树,其中1号点是根节点.Bob在每个点上涂了颜色,并且每个点上的颜色不同.定义一条路 径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色. ...

  4. S - Query on a tree HDU - 3804 线段树&plus;dfs序

    S - Query on a tree HDU - 3804   离散化+权值线段树 题目大意:给你一棵树,让你求这棵树上询问的点到根节点直接最大小于等于val的长度. 这个题目和之前写的那个给你一棵 ...

  5. HDU 5692 线段树&plus;dfs序

    Snacks Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Sub ...

  6. bzoj3252攻略&lpar;线段树&plus;dfs序&rpar;

    3252: 攻略 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 562  Solved: 238[Submit][Status][Discuss] D ...

  7. 【BZOJ-3779】重组病毒 LinkCutTree &plus; 线段树 &plus; DFS序

    3779: 重组病毒 Time Limit: 20 Sec  Memory Limit: 512 MBSubmit: 224  Solved: 95[Submit][Status][Discuss] ...

  8. 【BZOJ-3306】树 线段树 &plus; DFS序

    3306: 树 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 792  Solved: 262[Submit][Status][Discuss] De ...

  9. HDU5692&lpar;线段树&plus;dfs序)

    Snacks Time Limit:5000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Statu ...

随机推荐

  1. 数据结构之C语言实现哈夫曼树

    1.基本概念 a.路径和路径长度 若在一棵树中存在着一个结点序列 k1,k2,……,kj, 使得 ki是ki+1 的双亲(1<=i<j),则称此结点序列是从 k1 到 kj 的路径. 从 ...

  2. MyBatis——实现关联表查询

    原文:http://www.cnblogs.com/xdp-gacl/p/4264440.html 一.一对一关联 1.1.提出需求 根据班级id查询班级信息(带老师的信息) 1.2.创建表和数据 创 ...

  3. &lbrack;转载&rsqb;js javascript 判断字符串是否包含某字符串&comma;String对象中查找子字符&comma;indexOf

    var Cts = "bblText"; if(Cts.indexOf("Text") > 0 ) { alert('Cts中包含Text字符串'); }

  4. linux必会的60个命令

    ◆ 安装和登录命令:login.shutdown.halt.reboot.install.mount.umount.chsh.exit.last: ◆ 文件处理命令:file.mkdir.grep.d ...

  5. linux进程间通讯-System V IPC 信号量

    进程间通信的机制--信号量.注意请不要把它与之前所说的信号混淆起来,信号与信号量是不同的两种事物.有关信号的很多其它内容,能够阅读我的还有一篇文章:Linux进程间通信--使用信号.以下就进入信号量的 ...

  6. Delphi中TWebBrowser中注入Js

    最近帮朋友做一个软件,其中要自动化某网页中的操作,最简的操作是调用自己写的代码. 代码如下: procedure TForm1.Button2Click(Sender: TObject);var  i ...

  7. jquery之ajax中国乱码的解决方案

    $.ajax({ dataType : 'json',type : 'POST',url : 'http://localhost/test/test.do',data : {id: 1, type: ...

  8. 如何利用&period;Net内置类,解析未知复杂Json对象

    如何利用.Net内置类,解析未知复杂Json对象 如果你乐意,当然可以使用强大的第三方类库Json.Net中的JObject类解析复杂Json字串 . 我不太希望引入第三方类库,所以在.Net内置类J ...

  9. July 12th&comma; 2018&period; Thursday&comma; Week 28th&period;

    People love what other people are passionate about. 人总是会爱上别人倾注热情的事物. From La La Land. This quote has ...

  10. 关于gitee代码上传下载

    1.在gitee上面创建新分支: 2.复制本地ssh秘钥(C:\Users\Administrator\.ssh) 添加到 gitee设置页面的ssh:(如果之前没有秘钥,就执行ssh-keygen ...