P6594 [YsOI2020] 换寝室 —— 树形dp+二分答案
li_cat
·
·
个人记录
题意：给定一棵树，每条边有边权，割掉一些边，使得被割掉的边边权和不超过 k ，最小化剩余连通块点权极差的最大值
13pts
## 21pts
枚举每一条权值不为零的边打开或关闭，指数级别复杂度
## 正解
考虑dp
原本想到背包，将权值作为体积，但是割去每条边的价值会**不断变化，并不显然**
$$
_{//接下来均为看了题解之后的}
$$
- - -
我们发现，答案是随着k的增加**单调递减**的
发现满足单调性，考虑**二分答案**
二分答案 $res$ ，然后思考如何检验答案合法性
这个时候就可以发现代价很好dp了
设状态 $dp_{u,x}$ 为 $u$ 的子树都被合法地划分成若干个连通块， $u$ 此时属于以 $x$ 为最小值的联通块的最小代价
容易知道，只要点权 $val_u$ 在 $[val_x,val_x+res]$ 之内，它就有可能在其的连通块中；反之则不可能
节点对于每个其的每个孩子，都有割和不割两种选择(即加入连通块或断开)，于是可以得到状态转移方程
$$
dp_{u,x}=\sum_{v \in u's son} min(dp_{v,x},mn_v+cost_{u,v})
$$
其中 $cost_{u,v}$ 为断开 $u$ 与 $v$ 这条边的代价， $mn$ 为一个点能凑出的所有合法情况的最小值
(其实很好理解，我都断开了，它肯定无所谓怎么连，代价怎么小怎么来)
AC Code:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN=805;
const int inf=0x3f3f3f3f;
int n,m,k;
int dep[MAXN],fa[MAXN],siz[MAXN],hson[MAXN];
vector<int> edge[MAXN];
void dfs1(int x){
dep[x]=dep[fa[x]]+1;
siz[x]=1;
for(auto v:edge[x]){
if(v==fa[x]) continue;
fa[v]=x;
dfs1(v);
siz[x]+=siz[v];
if(!hson[x] || siz[v]>siz[hson[x]]) hson[x]=v;
}
}//
int top[MAXN];
void dfs2(int x,int h){
top[x]=h;
if(hson[x]) dfs2(hson[x],h);
for(auto v:edge[x]){
if(v==fa[x]) continue;
if(v==hson[x]) continue;
dfs2(v,v);
}
}//
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
return y;
}//
int delta[MAXN],cnt[MAXN];
bool block[MAXN];
void update(int x,int y){
delta[x]++;delta[y]++;delta[LCA(x,y)]-=2;
}//
int FirstDFS(int x){
int sum=0;
for(auto v:edge[x]){
if(v==fa[x]) continue;
sum+=FirstDFS(v);
}
sum+=delta[x];
if(!sum) block[x]=1;
cnt[x]=sum;
return sum;
}//
int difference[MAXN];
int mx[MAXN],mn[MAXN];
int GetUnsatisfaction(int x){
int res=0;
mx[x]=mn[x]=difference[x];
for(auto v:edge[x]){
if(v==fa[x]) continue;
res=max(res,GetUnsatisfaction(v));
if(block[v]) continue;
mx[x]=max(mx[x],mx[v]);
mn[x]=min(mn[x],mn[v]);
}
res=max(res,mx[x]-mn[x]);
return res;
}//
int ans;
int dp[MAXN][MAXN];
void DP(int x,int rs){
for(auto v:edge[x]){
if(v==fa[x]) continue;
DP(v,rs);
}
for(int i=1;i<=n;++i){
dp[x][i]=inf;
if(difference[x]<=difference[i]+rs && difference[x]>=difference[i]) dp[x][i]=0;
}
mn[x]=inf;
for(int i=1;i<=n;++i){
if(dp[x][i]>=inf) continue;
for(auto v:edge[x]){
if(v==fa[x]) continue;
dp[x][i]+=min(dp[v][i],mn[v]+cnt[v]);
}
mn[x]=min(mn[x],dp[x][i]);
}
}//
//void Getans(int i,int nk){
// if(i>n) return ;
// if(block[i]){
// Getans(i+1,nk);
// return;
// }if(nk<0){
// return;
// }
// Getans(i+1,nk);
//
// if(nk-cnt[i]<0) return ;
// block[i]=1;
// ans=min(ans,GetUnsatisfaction(1));
// Getans(i+1,nk-cnt[i]);
// block[i]=0;
//}//
int erf(int l,int r){
int mid=l+r>>1;
while(l<r){
DP(1,mid);
if(mn[1]<=k) r=mid;
else l=mid+1;
mid=l+r>>1;
}
return l;
}//
void work(){
int x,y;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i) scanf("%d",&difference[i]);
for(int i=1;i<n;++i){
scanf("%d%d",&x,&y);
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs1(1);
dfs2(1,1);
while(m--){
scanf("%d%d",&x,&y);
update(x,y);
}
FirstDFS(1);
int res=GetUnsatisfaction(1);
if(k==0){
printf("%d",res);
return ;
}
ans=erf(0,1e9+5);
printf("%d",ans);
}//
int main(){
work();
return 0;
}
```