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
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);
}