BZOJ[3252]攻略

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

一个类似长链剖分的东西。

直接把链按照权值剖分，取前k个最长的链

#include<bits/stdc++.h>

#define lll long long

using namespace std;

lll read(){

	lll x=0,w=1;char ch=getchar();

	while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return x*w;

}

const lll N=200010;

lll n,k,cnt,opt,ans,x,y;

lll a[N],head[N],son[N],sum[N],c[N];

struct node{

	lll to,next;

}edge[N];

bool cmp(lll p,lll q){return p>q;}

void add(lll x,lll y){

	cnt++;edge[cnt].to=y;edge[cnt].next=head[x];head[x]=cnt;

}

void dfs1(lll k){

	for(lll i=head[k];i;i=edge[i].next){

		lll v=edge[i].to;dfs1(v);

		sum[k]=max(sum[k],sum[v]);if(sum[v]>sum[son[k]])son[k]=v;

	}sum[k]+=a[k];

}

void dfs2(lll k,lll top){

	if(k==top)c[++opt]=sum[k];

	if(!son[k])return;

	dfs2(son[k],top);

	for(lll i=head[k];i;i=edge[i].next){

		lll v=edge[i].to;if(v==son[k])continue;

		dfs2(v,v);

	}

}

int main(){

	n=read();k=read();

	for(lll i=1;i<=n;i++)a[i]=read();

	for(lll i=1;i<n;i++){

		x=read();y=read();add(x,y);

	}dfs1(1);dfs2(1,1);sort(c+1,c+1+opt,cmp);

	for(lll i=1;i<=k;i++)ans+=c[i];

	printf("%lld\n",ans);return 0;

}

巴特西

BZOJ[3252]攻略（长链剖分）