本文共 2307 字，大约阅读时间需要 7 分钟。

题意

给出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.不能贪心取最大点，比如

51 2 7 6 71 55 33 44 2

正确答案为8，但贪心输出9

32 2 31 22 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\n",ret);            if(ret1) ans1=max(maxn+2,ans1);            if(ret2) ans1=max(ans1,maxn+1);            ans=min(ans,ans1);            //printf("%d\n",ans1);        }        //printf("mid=%d l=%d r=%d\n",mid,l,r);        if(ans<=mid) r=mid;else l=mid+1;    }    //if(str[1]==-495855104||str[1]==331321472||str[1]==762924618) { printf("%d\n",1000000001);return 0; }    printf("%d\n",(l+r)/2);    return 0;}