3252: 攻略
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
Source
题解：
如标签所说，dfs序+线段树。
我们可以发现取法是符合贪心性质的，每次找到一个点，使得它到根的权值和最大。。
用dfs序保证子树是一段连续的区间，然后用线段树维护最大值。
在把链取走的时候注意更新其他点的权值和。。。。
#include<stdio.h>
#include<iostream>
using namespace std;
const int N=200005;
#define ll long long
#define p1 (p<<1)
#define p2 (p<<1|1)
int n,m,i,x,y,k,a[N],id[N],b[N],fa[N],h[N],mx[N],q[N];
int tot,head[N],to[N],Next[N];
ll ans,t[N<<2],add[N<<2],sum[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
void Add(int x,int y)
{
to[tot]=y;
Next[tot]=head[x];
head[x]=tot++;
}
inline void dfs(int x,int pre)
{
id[x]=mx[x]=++k;
b[k]=x;
for(int i=head[x];i!=-1;i=Next[i]) if(to[i]!=pre)
{
fa[to[i]]=x;
sum[to[i]]=sum[x]+a[to[i]];
dfs(to[i],x);
mx[x]=max(mx[x],mx[to[i]]);
}
}
void build(int l,int r,int p)
{
if(l==r)
{
t[p]=sum[b[l]];
q[p]=l;
return;
}
int mid=(l+r)>>1;
build(l,mid,p1);build(mid+1,r,p2);
if(t[p1]>t[p2]) t[p]=t[p1],q[p]=q[p1];else
t[p]=t[p2],q[p]=q[p2];
}
void update(int l,int r,int x,int y,int z,int p)
{
if(x<=l&&r<=y)
{
t[p]+=z;add[p]+=z;
return;
}
int mid=(l+r)>>1;
if(add[p]!=0)
{
add[p1]+=add[p];add[p2]+=add[p];
t[p1]+=add[p];t[p2]+=add[p];
add[p]=0;
}
if(x<=mid) update(l,mid,x,y,z,p1);
if(y>mid) update(mid+1,r,x,y,z,p2);
if(t[p1]>t[p2]) t[p]=t[p1],q[p]=q[p1];else
t[p]=t[p2],q[p]=q[p2];
}
int main()
{
read(n),read(m);
for(i=1;i<=n;i++) read(a[i]),head[i]=-1;
for(i=1;i<n;i++)
{
read(x),read(y);
Add(x,y);
}
sum[1]=a[1];
dfs(1,0);
build(1,n,1);
while(m--)
{
ans+=t[1];
for(i=b[q[1]];!h[i]&&i;i=fa[i])
{
h[i]=1;
update(1,n,id[i],mx[i],-a[i],1);
}
}
cout<<ans;
return 0;
}