【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

Sample Output

HINT

对于100%的数据，n<=200000，1<=场景价值<=2^31-1

题解：由于原题就是一个费用流，所以本题我们依旧试图模拟一下费用流的过程。

先spfa找到一条最长路，然后将这些边的正向边流量变为0，再加入反向边。。。等等，加反向边好像没啥用？

因为我们永远也不会走反向边，那么我们只需要每次贪心的选取一条最长的路径即可。具体地，我们用线段树维护DFS序，位置i的值为从根节点到i的路径长度。每次找到最长路后，将路径上所有未被访问过的点都拿出来，更新一下它子树中所有点的路径长度即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#define lson x<<1

#define rson x<<1|1

using namespace std;

const int maxn=200010;

typedef long long ll;

int n,k,cnt;

ll ans;

int p[maxn],q[maxn],to[maxn<<1],next[maxn<<1],head[maxn<<1],fa[maxn],vis[maxn],org[maxn];

int ps[maxn<<2];

ll s[maxn<<2],tag[maxn<<2],dep[maxn],v[maxn];

int rd()

{

	int ret=0;	char gc=getchar();

	while(gc<'0'||gc>'9')	gc=getchar();

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret;

}

void add(int a,int b)

{

	to[++cnt]=b,next[cnt]=head[a],head[a]=cnt;

}

void dfs(int x)

{

	p[x]=++p[0],org[p[0]]=x;

	for(int i=head[x];i;i=next[i])	if(to[i]!=fa[x])	dep[to[i]]=dep[x]+v[to[i]],fa[to[i]]=x,dfs(to[i]);

	q[x]=p[0];

}

void pushup(int x)

{

	s[x]=max(s[lson],s[rson]);

	ps[x]=(s[lson]>=s[rson])?ps[lson]:ps[rson];

}

void pushdown(int x)

{

	if(tag[x])	s[lson]+=tag[x],s[rson]+=tag[x],tag[lson]+=tag[x],tag[rson]+=tag[x],tag[x]=0;

}

void build(int l,int r,int x)

{

	if(l==r)

	{

		s[x]=dep[org[l]],ps[x]=org[l];

		return ;

	}

	int mid=l+r>>1;

	build(l,mid,lson),build(mid+1,r,rson);

	pushup(x);

}

void updata(int l,int r,int x,int a,int b,int c)

{

	if(a<=l&&r<=b)

	{

		s[x]-=c,tag[x]-=c;

		return ;

	}

	pushdown(x);

	int mid=l+r>>1;

	if(a<=mid)	updata(l,mid,lson,a,b,c);

	if(b>mid)	updata(mid+1,r,rson,a,b,c);

	pushup(x);

}

int main()

{

	n=rd(),k=rd();

	int i,a,b,t;

	for(i=1;i<=n;i++)	v[i]=rd();

	for(i=1;i<n;i++)	a=rd(),b=rd(),add(a,b),add(b,a);

	dep[1]=v[1],dfs(1);

	build(1,n,1);

	for(i=1;i<=k;i++)

	{

		t=ps[1],ans+=s[1];

		while(t&&!vis[t])	vis[t]=1,updata(1,n,1,p[t],q[t],v[t]),t=fa[t];

	}

	printf("%lld",ans);

	return 0;

}

攻略