题解 [YsOI2020]换寝室
xiaolilsq
·
·
题解
题意简化后就是这样：
给定一棵树，每条边有边权，割掉一些边，使得被割掉的边边权和不超过 k ，最小化剩余连通块点权极差的最大值。
subtask 1
枚举割掉哪些边，判一下是否合法再更新一下答案。
时间复杂度： O(2^{n-1}) 。
subtask 2
最小化剩余连通块点权极差的最大值，考虑二分答案 mid ，题目转化为：
给定一棵树，要求割掉一些边后剩余连通块点权极差小于 mid ，最小化割掉的边边权和。
考虑 dp ，设状态 dp_{u,l,r} 表示考虑完了以 u 为根的子树，其中 u 这个点所在的联通块最小值所在点编号为 l ，最大值所在点编号为 r 的最小花费，每次都树形dp一遍判答案是否合法。
时间复杂度： O(n^3\log_2maxh) 。
subtask 3
树为一条链，直接转区间问题，设 dp_r 表示考虑完了前 1\sim r 个点最小的花费，直接枚举每一个合法的 l ，把 l\sim r 作为一个连通块进行转移就行了。
可以用单调队列进一步优化。
时间复杂度： O(n\log_2maxh) 。
subtask 4
树为一朵盛开的菊花，割掉一条边就是割掉根与叶子节点，最后的连通块要么和根节点连着，要么大小为1，离散化所有点权，双指针 l 和 r 表示把点权在 l 到 r 之间节点的作为和根节点连着的连通块，其他的点作为单独连通块，直接扫一遍可以得到答案。
时间复杂度： O(n\log_2maxh) 。
所以其实subtask3和subtask4的复杂度可以更优，原本可以出个数据分治屑题的。
subtask 5
时间复杂度： $O(n)$ 。
## subtask 6
考虑优化subtask 2里面讲的算法。
发现不必最大值和最小值都记录，只要记录一个即可。
二分出 $mid$ 后，首先对于所有点，dfs出所有可以以它为最小值的点。
如果两个点的最小值所在点编号相同，那么它们在同一个连通块。
转移如下：
$$dp_{u,x}=\sum_{v\ is\ u's\ son}\min(dp_{v,y}+val_{u,v},dp_{v,x})$$
其中要求 $x,y$ 合法（即点 $u$ 所在连通块的最小值所在点编号可以是 $x$ ，点 $v$ 同理，可以用 $n$ 遍 $\rm dfs$ 预处理出来）。
时间复杂度： $O(n^2\log_2maxh)$ 。
最后放一下标程：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
template<typename T>void read(T &x){
x=0;int f(1);char c(getchar());
for(;!isdigit(c);c=getchar())if(c=='-')f=-f;
for(; isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c-'0');
x*=f;
}
template<typename T>void write(T x){
if(x<0)putchar('-'),x=-x;
if(x/10)write(x/10),x%=10;
putchar(x+'0');
}
const int maxn=808;
struct Edge{
int v,nt;
Edge(int v=0,int nt=0):
v(v),nt(nt){}
}e[maxn*2];
int hd[maxn],num;
void add_edge(int u,int v){
e[++num]=Edge(v,hd[u]);hd[u]=num;
}
int dep[maxn],pa[maxn][12];
void dfs0(int u,int fa,int dp){
dep[u]=dp;pa[u][0]=fa;
for(int i=1;(1<<i)<=dp;++i)
pa[u][i]=pa[pa[u][i-1]][i-1];
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(v==fa)continue;
dfs0(v,u,dp+1);
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int t=dep[x]-dep[y],cn=0;t;t>>=1,++cn)
if(t&1)x=pa[x][cn];
if(x==y)return x;
for(int i=11;i>=0;--i)
if(pa[x][i]!=pa[y][i])
x=pa[x][i],y=pa[y][i];
return pa[x][0];
}
int vis[maxn];
void dfs1(int u,int fa){
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(v==fa)continue;
dfs1(v,u);
vis[u]+=vis[v];
}
}
int Base,lo[maxn][maxn],h[maxn];
void dfs2(int u,int fa,int ac){
lo[ac][u]=true;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(v==fa||h[v]<h[ac]||h[v]-h[ac]>Base)
continue;
dfs2(v,u,ac);
}
}
int n,dp[maxn][maxn];
void dfs3(int u,int fa){
for(int i=1;i<=n;++i)
if(lo[i][u])dp[i][u]=0;
else dp[i][u]=inf;
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(v==fa)continue;
dfs3(v,u);
int mn=inf;
for(int j=1;j<=n;++j)
mn=min(mn,dp[j][v]);
mn+=vis[v];
for(int j=1;j<=n;++j)
if(dp[j][u]<inf)
dp[j][u]+=min(mn,dp[j][v]);
}
}
int judge(int pos){
Base=pos;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
lo[i][j]=0;
dfs2(i,0,i);
}
dfs3(1,0);
int ans=inf;
for(int i=1;i<=n;++i)
ans=min(ans,dp[i][1]);
return ans;
}
int main(){
int m,k,l=inf,r=-inf;
read(n),read(m),read(k);
for(int i=1;i<=n;++i){
read(h[i]);
l=min(l,h[i]);
r=max(r,h[i]);
}
for(int i=1;i<n;++i){
int u,v;
read(u),read(v);
add_edge(u,v);
add_edge(v,u);
}
dfs0(1,0,0);
while(m--){
int x,y;
read(x),read(y);
++vis[x],++vis[y];
vis[lca(x,y)]-=2;
}
dfs1(1,0);
r=r-l,l=0;
while(l+1<r){
int mid=(l+r)>>1;
if(judge(mid)<=k)
r=mid;
else
l=mid+1;
}
if(judge(l)<=k)
write(l);
else
write(r);
putchar('\n');
return 0;
}
```