场上一眼二分，然后想了 $5$ 分钟差不多了。

跟这道题的思想很像，每次二分是否能到达 $\ge x$ 的点，然后就可以把所有 $\ge x$ 的点染成黑色了，这时青木君就只需要管黑点了。

定义 $dp[i]$ 为要将 $i$ 子树下的所有黑点（不包括 $i$ 本身）变成 $0$ 所需要的额外染色次数。

则可以得到方程：

$$dp[i]=max(\sum_{j\in son_i}dp[j] + \sum_{j\in son_i}b[j]-1,0)$$

$b[i]$ 为 $i$ 的颜色，减一是因为本来 $i$ 点就有一次染色次数，取 $max$ 是因为子树之间互不干扰，即你不能用你隔壁子树的次数来填补你的窟窿。

然后就差不多了，$20$ 分钟场切（不是你也没告诉我二分边界可以是 $0$ 啊）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
vector<int>G[N];
int dp[N],a[N],b[N],n;
void dfs(int x,int f)
{
	int sum=0;
	for(int y:G[x])if(y!=f)
	{
		dfs(y,x);
		if(b[y])sum++;
		sum+=dp[y];
	}
	sum=max(0ll,sum-1);
	dp[x]=sum;
}
bool check(int x)
{
	for(int i=1;i<=n;i++)b[i]=a[i]>=x;
	dfs(1,0);
	return dp[1]>0;
}
signed main()
{
	cin>>n;
	for(int i=2;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	int l=0,r=1e9,ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1,ans=mid;
		else r=mid-1;
	}
	cout<<ans;
	return 0;
}