BZOJ#3252 题解

First Post:

Last Update:

第一次做到这种类似长剖的贪心题. 故记之.

BZOJ#3252#

给定 个点的树 和 , 点带权 . 一个方案是 条从根开始到某个叶子结束的路径, 定义一个方案的价值是这个方案里的所有路径经过点的并集中的所有点的点权和. 求一种方案最大化价值, 只需要输出这个方案的价值即可.

首先我们对每个节点 记 , 然后我们记 是 的儿子且满足 , 只保留 向 的连边, 树变成了若干链. 记一条链 的顶点是其中父亲节点不在链中的节点 . 一条链的权值为 . 我们证明: 最优方案的权值就是这些链的权值中前 大的权值的加和.

我断言以下方案可以增量式的构造一个合法的答案: 每次取出从根到某个叶子点权和最大的一条链, 那以后给答案加上那个和, 再让这条链上的所有点权变为 0. 可以这么证明: 对于树, 考虑 是到根路径权值和最大的叶子, 我们来证至少存在一种最优解包含. 用调整法: 假设某个最优解 不包含 , 那么考虑 和 中被选的叶子点集的 , 记为 , 和 的 LCA 为 的 中的叶子记为 , 则由于 到根路径最大, 不小于 到根路径, 所以 到 路径也不小于 到 路径, 那么把 中的 换成 可以得到一个权值不小于 的方案 . (感谢 LCA 在 LA 教我).

其实这个过程可以用长链剖分维护, 由于要 NOIOL 所以证明先咕着.

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
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x, i##end=y; i<=i##end; ++i)
#define d(i,x,y) for(int i=y, i##end=x; i>=i##end; --i)
#define uf(i,x,y) for(int i=x, i##end=y; i<i##end; ++i)
#define ll long long
#define pir pair<int, int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back 
#define int ll
char ch;
int rd() {
  int f=1, x=0; ch=getchar();
  while(!isdigit(ch)) { f=((ch=='-')?-1:f); ch=getchar(); }
  while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
  return x*f;
}
void rd(int& x) { x=rd(); }
using namespace std;
#define _ 200005
int height[_], val[_], son[_], fa[_], n, k; vector<int> edge[_];
void dfs(int u, int f) {
  fa[u]=f;
  for(auto v:edge[u]) {
    if(v==f) continue ;
    dfs(v, u); if(height[v] >= height[son[u]]) son[u]=v;
  }
  height[u]=height[son[u]]+val[u];
}
signed main() {
  rd(n); rd(k); f(i,1,n) rd(val[i]); f(i,1,n-1) {
    int u=rd(), v=rd();
    edge[u].pb(v); edge[v].pb(u);
  }
  dfs(1, 0); ll ans=0; f(i,1,n) if(son[fa[i]] == i) height[i]=0;
  sort(height+1, height+n+1, [](int u, int v){return u>v;});
  f(i,1,k) ans += height[i];
  cout << ans << endl;
  return 0;
}