题解：P6594 [YsOI2020] 换寝室
RB211_535E4B
·
·
题解
提示部分
建议按顺序看提示。
::::info[1.使用算法]
二分与 DP。
其实还有树上差分，不过是辅助用的。
::::
::::info[2.二分什么值]
二分答案小朋友们的总不满意值。
此值满足二分单调性。
::::
::::info[3.DP 状态设定]
::::
::::info[4.DP 转移]
目前讨论 $x$，定讨论 $x$ 的孩子 $y$ 对 $dp_{x,j}$ 的贡献。
贡献为：
$$ \min(dp_{y,j}, Min_y + w(x,y)) $$
其中 $Min_y$ 代表 $\displaystyle \min_{j=1}^{n} dp_{y,j}$，$w(x,y)$ 代表这条边被几个老师包含。
::::
若你把所有提示内容都想正确，那么你的做法大概率正确。
但是你如果看不懂或者没想出来，请看下面的讲解。
## 讲解
### 使用算法
本题使用二分与动规，还有树上差分辅助处理老师路径。
为何使用二分？因为若小朋友们的总不满意值变大，那么所有老师的不满意值之和会变小。
### 二分什么值
从上文。
> 若小朋友们的总不满意值变大，那么所有老师的不满意值之和会变小。
可以看出可以二分小朋友们的总不满意值。
### DP 状态设定
如何判断目前 $mid$ 是否合法？我们将使用树上 DP 算法处理。
若只设 $dp_i$ 代表讨论到 $i$ 为根的子树，最小老师的不满意值之和。
可发现无法处理最大值与最小值。
但若设 $dp_{i,j,k}$ 代表讨论到 $i$ 为根的子树，与 $i$ 相连的连通块的值中，最大值为 $h_j$，最小值为 $h_k$，最小老师的不满意值之和。但是会超空间。
注意到连通块的值在 $mid$ 的限制下可视为一个区间，即某连通块的值可以在一个长度为 $mid$ 的区间中（但是不一定要占满），此时可以得出状态。
$dp_{i,j}$ 代表讨论到 $i$，与 $i$ 相连的连通块的值在 $[h_j - mid, h_j]$ 之间，最小老师的不满意值之和。
### DP 转移
目前讨论 $x$，定讨论 $x$ 的孩子 $y$ 对 $dp_{x,j}$ 的贡献。
对于 $(x,y)$ 这条边有两种取法，取或不取。
$dp_{x,j}$ 加上两种取法中最小值即可。
#### 取
必定只能由 $dp_{y,j}$ 而来，第二维的值必须一样，即区间一样。
因为如果某情况在状态 $[h_k - mid, h_k](k \ne j)$ 中没有占满，此时可以为 $[h_j - mid, h_j]$ 更新，但是状态 $[h_j - mid, h_j]$ 也一定考虑了这种状态，所以 $[h_j - mid, h_j]$ 一定满足且最值。
若取状态 $[h_k - mid, h_k](k \ne j)$，那么可能会超出范围，而且不值，所以只从 $dp_{y,j}$ 而来。
#### 不取
这就是显而易见的了，若不取，上一个连通块是啥我们也不用管，加上权值即可。
#### 转移部分代码
```
MAX为极大值
Min[x] = MAX;
for (int j = 1; j <= n; j++){
for (int i = 0; i < a[x].size(); i++){
int y = a[x][i];
dp[x][j]+=min(dp[y][j],Min[y]+sum[y]);
dp[x][j] = min(dp[x][j],MAX);
}
Min[x] = min(Min[x],dp[x][j]);
}
```
### 其他杂事
初始化 DP 就是看看 $i (1 \le i \le n)$ 是否可以与 $x$ 在一起，即若 $h_x$ 不在 $i$ 所对应的区间里，设为无穷大。
### 代码
```
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e9;
int h[803];int n,m,k;
vector <int> a[808];
int sum[808],flag[808];
int fa[808][30];
int d[808];
int Min[808];
int dp[808][808];//讨论到i，与i相连的连通块的值在[h[j]-mid,h[j]]之间，老师的不满意值之和
void dfs(int x,int f,int id){
if (id == 1) sum[x] = flag[x];
if (id == 0) {
d[x] = d[f]+1;
fa[x][0] = f;
for (int i = 1; (1<<i) <= d[x]; i++) fa[x][i]=fa[fa[x][i-1]][i-1];
}
for (int i = 0; i < a[x].size(); i++){
int y = a[x][i];
if (y != f) {
dfs(y,x,id);
sum[x] += (id?sum[y]:0);
}
}
}
void dfs2(int x,int f,int mid){
for (int i = 0; i < a[x].size(); i++){ int y = a[x][i]; if (y != f) dfs2(y,x,mid);}
for (int i =1; i <= n; i++){
if (h[i]-mid > h[x] || h[i] < h[x]) dp[x][i] = MAX;//不可能在一起(不在这个区间)
else dp[x][i] = 0;
}
Min[x] = MAX;
for (int j = 1; j <= n; j++){
for (int i = 0; i < a[x].size(); i++){
int y = a[x][i];
dp[x][j]+=min(dp[y][j],Min[y]+sum[y]);
dp[x][j] = min(dp[x][j],MAX);
}
Min[x] = min(Min[x],dp[x][j]);
}
}
int lca(int x,int y){
if (d[x] <= d[y]) swap(x,y); for (int i = 21; i >= 0; i--) if (d[x]-(1<<i) >= d[y]) x = fa[x][i];
if (x == y) return x; for (int i = 21; i>= 0; i--) if (fa[y][i] != fa[x][i]) x = fa[x][i],y = fa[y][i]; return fa[x][0];
}
int check(int x){
dfs2(1,0,x);
return Min[1];
}
int main(){
cin >> n >> m >> k;
int max_ = 0;
for (int i = 1; i <=n; i++) cin >> h[i],max_ = max(max_,h[i]);
for (int i = 1; i <= n-1; i++){
int u,v; cin >> u >>v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1,0,0);
for (int i = 1; i <= m; i++){
int x,y; cin >> x >> y;
flag[x] ++,flag[y] ++;//标记
flag[lca(x,y)]-=2;
}
dfs(1,0,1);
int l = 0,r = max_,ans = MAX;//简单二分答案小朋友们的总不满意值
while (l <= r){
int mid = (l+r)/2;
if (check(mid)<=k) ans = mid,r = mid-1;
else l = mid+1;
}
cout << ans;
return 0;
}
```