链接：http://codeforces.com/problemset/problem/796/C
题意：就是说有一排银行相互联通，比如A,B,C，A和B连，B和C连，连成一串，现在问你要把这些银行全部hack掉，电脑所需要的最低限度是多少。
题解：这题比赛的时候没想出来，看错题目的意思，我还以为是我们正在学的最小生成树，以为是个贪心，没仔细看题，只有邻居或者半相邻才可能强度加1，并不是hack掉一个的时候，所有的都增加1，所以每个银行最多加2，那么最后答案只可能在max,max+1,max+2中产生，所以需要我们讨论一下强度为max和max-1的银行中产生最大值，然后对他进行分类讨论，就可以得到答案了。
代码
#include <iostream> #include <set> #include <vector> #include <cstring> #include <string> #include <stdio.h> #define maxn 300005 #define INF 0x3fffffff using namespace std; vector<int> a[maxn]; int s[maxn]; int n; typedef long long LL; void solve() { int i,mx,ans,num1,num2,num3,counter,k,j; mx=-INF; num1=num2=num3=0; j=0; for(i=1;i<=n;i++) { mx=max(mx,s[i]); } for(i=1;i<=n;i++) { if(s[i]==mx) { num1++; k=i; } else if(s[i]==mx-1)num2++; } if(num1==1) { counter=0; for(i=0;i<a[k].size();i++) { if(s[a[k][i]]==mx-1)counter++; } if(counter==num2)ans=mx; else ans=mx+1; } else { int flag; flag=0; for(i=1;i<=n;i++) { counter=0; for(j=0;j<a[i].size();j++) { int v; v=a[i][j]; if(s[v]==mx)counter++; } if(s[i]==mx)counter++; if(counter==num1)flag=1; } if(flag)ans=mx+1; else ans=mx+2; } cout<<ans<<endl; } int main() { int i,start,end; while(cin>>n) { memset(s,0,sizeof(s)); for(i=1;i<=n;i++) { cin>>s[i]; a[i].clear(); } for(i=0;i<n-1;i++) { scanf("%d%d",&start,&end); a[start].push_back(end); a[end].push_back(start); } solve(); } return 0; }