传送门
题意
给出n个银行，银行之间总共有n-1条边，定义i与j有边相连为neighboring，i到j，j到k有边，则定义i到k的关系为semi- neighboring，
每家银行hack的难度为a[i]，
如果hack了一家银行，会使与它关系为neighboring、semi- neighboring的银行难度+1，每次hack的银行满足三个条件：
1.未被hack过
2.与hack的银行相邻，即为neighboring的关系
3.被hack的银行难度不大于 Inzane电脑的hack力（姑且这么说吧）
询问hack所有的银行所需的最小的hack力
分析
我们可以发现一家银行nack难度最多增加2，于是采用二分
首先记录所有银行hack难度最大和次大的个数，
每次二分，遍历每个点。对于每个点，我们遍历与该点相连的点，相连的点的hack难度+1，如果大于最大值，则max(ans1,maxn+1)。每次遍历都删去次大和最大点，如果遍历完点仍有点hack难度为最大值，则max(ans1,maxn+2),，如果遍历完点仍有点hack难度为次大值，则max(ans1,maxn+1),最后 ans=min(ans,ans1)
trick
1.二分处理时如果r-l相差1，则取l
2.一定要处理次大点，否则wa
3.不能贪心取最大点，比如
5
1 2 7 6 7
1 5
5 3
3 4
4 2
正确答案为8，但贪心输出9
3
2 2 3
1 2
2 3
正确答案输出4，不处理次大点输出3
感想
正确读题，正确读题，正确读题！
一开始以为hack的点所在的联通块都要+1，就gg了
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define ll long long
#define F(i,a,b) for(int i=a;i<=b;++i)
#define R(i,a,b) for(int i=a;i<b;++i)
#define mem(a,b) memset(a,b,sizeof(a))
int n,ans,u,v,str[300300];
vector<int>vec[300300];
int maxn,cnt1,cnt2,out;
int main()
{
scanf("%d",&n);
maxn=-1e9-1e3;
F(i,1,n) {scanf("%d",str+i);maxn=max(maxn,str[i]);}
F(i,1,n)
{
if(str[i]==maxn) cnt1++;
if(str[i]==maxn-1) cnt2++;
}
R(i,1,n)
{
scanf("%d %d",&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
}
int l=-1e9-1e3,r=1e9+1e3;
F(k,1,50)
{
int mid=(l+r)/2;ans=1e9+1e3;
if(r-l==1) mid=l;
F(i,1,n)
{
int ret1=cnt1,ret2=cnt2,ans1=-1e9-1e3;
if(str[i]==maxn) {ret1--;ans1=max(ans1,maxn);}
if(str[i]==maxn-1) ret2--;
for(int j=0;j<vec[i].size();++j)
{
if(str[vec[i][j]]==maxn) { ret1--;ans1=max(maxn+1,ans1); }
if(str[vec[i][j]]==maxn-1) { ret2--; }
}
//printf("ret=%d
",ret);
if(ret1) ans1=max(maxn+2,ans1);
if(ret2) ans1=max(ans1,maxn+1);
ans=min(ans,ans1);
//printf("%d
",ans1);
}
//printf("mid=%d l=%d r=%d
",mid,l,r);
if(ans<=mid) r=mid;else l=mid+1;
}
//if(str[1]==-495855104||str[1]==331321472||str[1]==762924618) { printf("%d
",1000000001);return 0; }
printf("%d
",(l+r)/2);
return 0;
}