下午刷题的时候突然发现洛谷评测机变卡了？才发现有月赛就去试了一发div1（结果当然是被吊打）
# 题面
> 洛谷 P6748
点击展开/折叠题面
L 国有 $n$ 个城市，它们之间有 $n-1$ 条道路，形成了一棵树的结构。
国王 L 派遣了一些军队来驻守这些道路，驻守每一条道路的军队战斗力都可以被量化为 $[1,m]$ 中的整数。
每个城市都有一个城主，第 $i$ 个城主有一个忍耐度 $a_i$。如果国王 L 在与第 $i$ 个城市相连的所有道路上驻守的军队战斗力的中位数超过了城主的忍耐度，那么城主就会认为国王不信任他而产生谋反的心理。
国王 L 当然不希望有人造反，但他又想使驻守道路的军队的总战斗力最大来保证国防安全。现在他找到了 L 国最强的 OIer —— 您，去来帮助他解决这个问题。
如果无论如何安排军队都会有人想要造反，那么输出 -1。
注：对于任意 $k$ 个数，它们的中位数是将这些数从小到大排序后第 $\left\lfloor\dfrac{k}{2}\right\rfloor+1$ 个数。
# 解析
没怎么想最暴力的部分……直接从DP开始分析吧。
先转换中位数的限制——任意一个点 $u$ 相邻的边中至少有 $\left\lfloor\frac{du_u}2\right\rfloor+1$ 条的权值 $\le a_u$。
于是考虑点与点之间的关系，在本题中就只需考虑父子之间的关系，换句话说，当前点与其父亲之间的边的取值。
可以设计DP状态 $f_{u,0},f_{u,1}$ 分别表示 $u$ 到其父亲的边的权值 $w$ 的范围为 $[1,a_u],(a_u,m]$ 时 $u$ 子树内的最大边权和（可能不合法，设为 $-1$）。
然后就可以分类讨论转移了，设父亲的点权为 $a_v$，贪心地想，若当前边权的可取值是一个区间，则一定取到区间的最大值：
- 当 $w\in[1,a_u]$ 时
- 可以贡献一条 $\le a_v$ 的边，则边权取值为 $\min\{a_u,a_v\}$；
- 当 $a_u>a_v$ 时，可以贡献一条 $>a_v$ 的边，边权为 $a_u$。
- 当 $w\in(a_u,m]$ 时
- 当 $a_u< a_v$ 时，可以贡献一条 $\le a_v$ 的边，边权为 $a_v$；
- 当 $a_v< m$ 时，可以贡献一条 $>a_v$ 的边，边权为 $m$。
对于 $v$，我们要求至少有 $\left\lfloor\frac{du_v}2\right\rfloor+1$ 条边的权值不大于 $a_v$。于是有一个朴素的想法就是对每个点做一个背包，求出 $v$ 的所有与子节点的连边中有 $k$ 条不大于 $a_v$ 的边的最大DP值之和。
但是这样的背包是 $O(n^2)$ 的。
不妨假设所有既可以取 $[1,a_v]$ 也可以取 $(a_v,m]$ 的边都取值在 $(a_v,m]$，然后我们考虑将一些边替换为 $[1,a_v]$ 的取值，使得DP值减小尽可能少。
也就是说，设 $u$ 对 $v$ 贡献 $[1,a_v]$ 的边时的 DP 值为 $key_0$，贡献 $(a_v,m]$ 的边时 DP 值为 $key_1$；则所有边都取 $key_1$，然后向一个大根堆中插入 $(key_0-key_1)$。
一直弹大根堆的堆顶直到不大于 $a_v$ 的边足够多，就可以算出 $f_{v,0/1}$。
复杂度 $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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int Ri(){
register int r=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
return r;
}
typedef long long ll;
const int N=5e5+10;
struct GRAPH{
int head[N],nxt[N<<1],to[N<<1],ncnt;
void AddEdge(int u,int v){
int p=++ncnt,q=++ncnt;
nxt[p]=head[u],to[p]=v,head[u]=p;
nxt[q]=head[v],to[q]=u,head[v]=q;
}
int operator [](const int &u){return head[u];}
}Gr;
int n,m;
int lim[N];
ll f[N][2];
priority_queue< ll > que;
void DP(int u,int fa){
int du=0;
for(int it=Gr[u];it;it=Gr.nxt[it]){
int v=Gr.to[it];
du++;
if(v==fa) continue;
DP(v,u);
}
int les=0;
long long small=0,big=0;
while(!que.empty()) que.pop();
for(int it=Gr[u];it;it=Gr.nxt[it]){
int v=Gr.to[it];
if(v==fa) continue;
long long key0=-1,key1=-1;
if(~f[v][0]) key0=max(key0,min(lim[u],lim[v])+f[v][0]);
if(lim[v]<lim[u] && (~f[v][1])) key0=max(key0,lim[u]+f[v][1]);
if(lim[u]<m && (~f[v][1])) key1=max(key1,m+f[v][1]);
if(lim[u]<lim[v] && (~f[v][0])) key1=max(key1,lim[v]+f[v][0]);
if(key0==-1 && key1==-1){
printf("-1\n");
exit(0);
}
if(key0==-1 && key1!=-1) big+=key1;
if(key0!=-1 && key1==-1) les++,small+=key0;
if(key0!=-1 && key1!=-1) que.push(key0-key1),big+=key1;
}
while(!que.empty() && les<du/2){
big+=que.top();
que.pop();
les++;
}
f[u][0]=f[u][1]=-1;
if(les>=du/2) f[u][0]=big+small;
while(!que.empty() && les<du/2+1){
big+=que.top();
que.pop();
les++;
}
if(les>=du/2+1) f[u][1]=big+small;
}
int main(){
n=Ri(),m=Ri();
for(int i=1;i<=n;i++) lim[i]=Ri();
for(int i=1;i<n;i++) Gr.AddEdge(Ri(),Ri());
DP(1,0);
printf("%lld\n",f[1][1]);
return 0;
}
|
THE END
Thanks for reading!
> Linked 梦回还-Bilibili