攻略

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1169 Solved: 554
[Submit][Status][Discuss]

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

HINT

　　分析：

　　网上大部分人好像都是用的$dfs$序+线段树，实际上不用那么麻烦，直接上树链剖分，加个贪心就行了。

　　对于这道题，肯定要优先选取从起点（不一定是根，因为走过的路径不能重复算，所以有的路径走过以后会影响其他路径）到叶子节点权值和最大的路径，这显然就是树链剖分的轻重链/长短链（广义上）的思想，不过这里把剖分的标准换成权值和就行了。

　　剖分完以后，$top[]$值等于自身的节点就是一条路径的起点，我们把它的权值和丢进大根堆里维护然后取前$k$大就行了。

　　Code：

//It is made by HolseLee on 9th Nov 2018

//BZOJ 3252

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2e5+;

int n,m,head[N],cnte,fa[N],hson[N],top[N];

ll a[N],siz[N],ans;

struct Edge { int to,nxt; }e[N<<];

priority_queue<ll>q;

inline ll read()

{

    char ch=getchar(); ll x=; bool flag=false;

    while( ch<'' || ch>'' ) {

        if( ch=='-' ) flag=true; ch=getchar();

    }

    while( ch>='' && ch<='' ) {

        x=x*+ch-''; ch=getchar();

    }

    return flag ? -x : x;

}

inline void add(int x,int y)

{

    e[++cnte].to=y; e[cnte].nxt=head[x];

    head[x]=cnte;

}

void dfs1(int x)

{

    siz[x]=a[x];

    for(int i=head[x],y; i; i=e[i].nxt) {

        y=e[i].to;

        if( y==fa[x] ) continue;

        fa[y]=x; dfs1(y);

        siz[x]=max(siz[x],siz[y]+a[x]);

        if( siz[y]>siz[hson[x]] ) hson[x]=y;

    }

}

void dfs2(int x,int nowtop)

{

    top[x]=nowtop;

    if( !hson[x] ) return;

    dfs2(hson[x],nowtop);

    for(int i=head[x],y; i; i=e[i].nxt) {

        y=e[i].to;

        if( y==fa[x] || y==hson[x] ) continue;

        dfs2(y,y);

    }

}

int main()

{

    n=read(); m=read();

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

    int x,y;

    for(int i=; i<n; ++i) {

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

        add(x,y), add(y,x);

    }

    dfs1(); dfs2(,);

    for(int i=; i<=n; ++i)

    if( top[i]==i ) q.push(siz[i]);

    while( (m--) && (!q.empty()) ) {

        ans+=q.top(); q.pop();

    }

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

    return ;

}

攻略