bzoj 3252 攻略

题目描述

题目描述

题目简述：树版[k取方格数]

众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。今天他得到了一款新游戏《XX

半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状

结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同

时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观看多次是不能重复得到价值的）

“为什么你还没玩就知道每个场景的价值呢？”

“我已经看到结局了。”

输入格式

第一行两个正整数n,k

第二行n个正整数，表示每个场景的价值

以下n-1行,每行2个整数a,b，表示a场景有个选择支通向b场景（即a是b的父亲）

保证场景1为根节点

n<=200000，1<=场景价值<=2^31-1

输出格式

输出一个整数表示答案

样例

样例输入

		5 2
>4 3 2 1 1
>1 2
>1 5
>2 3
>2 4

样例输出

>10

Solution

大概就是选 $k$ 个叶子，然后把根到这些叶子的路径覆盖，求最大值

能够发现实际上就是长链剖分后选前 $k$ 长的链

#include <iostream>
#include <algorithm>
#include <vector>
#define maxn 200010
#define ll long long 
using namespace std;

int n, k, a[maxn];

struct Edge {
    int to, next, w;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int son[maxn]; ll mxd[maxn], dep[maxn];
void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        mxd[v] = dep[v] = dep[u] + a[v]; dfs(v, u);
        if (mxd[v] > mxd[u]) mxd[u] = mxd[v], son[u] = v;
    }
}

int top[maxn];
void dfs(int u, int fa, int topf) {
    top[u] = topf;
    if (son[u]) dfs(son[u], u, topf); 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue;
        dfs(v, u, v);
    } 
} 

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    for (int i = 1; i < n; ++i) {
        int x, y, z; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
    } dep[1] = mxd[1] = a[1]; dfs(1, 0); dfs(1, 0, 1); 
    vector<ll> A; 
    for (int i = 1; i <= n; ++i) 
        if (top[i] == i) A.push_back(mxd[i] - dep[i] + a[i]);
    sort(A.begin(), A.end(), greater<ll>());
    ll ans = 0; 
    for (int i = 0; i < min(k, (int) A.size()); ++i) ans += A[i];
    cout << ans << "\n"; 
    return 0;
}