Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

BZOJ 3252. 攻略

发表于 分类于
本文字数： 4.2k 阅读时长 ≈ 4 分钟

BZOJ 3252. 攻略

Algorithm I

考虑贪心，每次尽可能选择当前最大的答案，正确性易证。为了防止选择重复的点，考虑广义长链剖分，一定只会选择链顶到叶子的路径。将所有链排序，选择前 $k$ 大即可。复杂度 $O(n \log n)$ 。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <vector>
#define eb emplace_back
#include <algorithm>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef long long L;
const int N = 2e5 + 10;
L d[N];
vector <L> f;
vector <int> g[N];
int n, m, w[N], p[N], son[N], top[N];
void dfs1 (int u)
{
    for (int v : g[u]) if (v ^ p[u])
    {
        p[v] = u;
        dfs1(v);
        d[u] = max(d[u], d[v]);
        if (d[v] > d[son[u]]) son[u] = v;
    }
    d[u] += w[u];
}
void dfs2 (int u, int t)
{
    top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int v : g[u])
        if (v ^ p[u] && v ^ son[u]) dfs2(v, v);
}
int main ()
{
    read(n, m);
    for (int i = 1; i <= n; ++i) read(w[i]);
    for (int i = 1, a, b; i < n; ++i)
        read(a, b), g[a].eb(b), g[b].eb(a);
    dfs1(1), dfs2(1, 1);
    for (int i = 1; i <= n; ++i)
        if (top[i] == i) f.eb(d[i]);
    sort(f.begin(), f.end());
    L res = 0;
    for (int i = 0; i < m && i < f.size(); ++i)
        res += f[f.size() - i - 1];
    write(res);
    return 0;
}

Algorithm II

考虑树形 DP ，设 $f _ (u, k)$ 表示 $u$ 向下用 $k$ 条链覆盖的最大权值。那么有：

$$
f(u, k) = \max _ {i = 0} ^ k {f(u, i) + f(v, k - i)}
$$

对于 $k > 0$ ，再加上 $w _ i$ ，形式为 $(max, +)$ 卷积，发现有凸性，考虑闵可夫斯基和，用堆维护差分序列。合并时，使用堆的启发式合并。复杂度为 $O(n \log ^ 2 n)$ 。

查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <queue>
#include <vector>
#define eb emplace_back
#include <algorithm>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef long long L;
const int N = 2e5 + 10;
vector <int> g[N];
int n, m, w[N], id[N];
priority_queue <L> q[N];
void merge (int a, int b)
{
    if (q[id[a]].size() < q[id[b]].size()) swap(a, b);
    while (!q[id[b]].empty()) q[id[a]].push(q[id[b]].top()), q[id[b]].pop();
    id[b] = id[a];
}
void dfs (int u, int fa)
{
    for (int v : g[u]) if (v ^ fa)
        dfs(v, u), merge(u, v);
    auto &p = q[id[u]];
    if (p.empty()) p.push(w[u]);
    else
    {
        L t = p.top(); p.pop();
        p.push(t + w[u]);
    }
}
int main ()
{
    read(n, m);
    for (int i = 1; i <= n; ++i) id[i] = i;
    for (int i = 1; i <= n; ++i) read(w[i]);
    for (int i = 1, a, b; i < n; ++i)
        read(a, b), g[a].eb(b), g[b].eb(a);
    dfs(1, 0);
    L res = 0;
    auto &p = q[id[1]];
    for (; m && !p.empty(); --m, p.pop())
        res += p.top();
    write(res);
    return 0;
}
相关文章