自动搬运

查看原文

来自洛谷，原作者为

	xiaolilsq 灰名不比红名好看（

搬运于2025-08-24 22:22:16，当前版本为作者最后更新于2020-05-19 21:41:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意简化后就是这样：

给定一棵树，每条边有边权，割掉一些边，使得被割掉的边边权和不超过 $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

$k=0$ ， 当且仅当边权为 $0$ 时可以被割掉，割掉后直接dfs即可。

时间复杂度： $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)$ 。

最后放一下标程：

#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;
}