http://codeforces.com/contest/796/problem/C
题意:给一颗树，删除节点，每次删除节点会使未被删除邻居和未被删除邻居的邻居权+1，问删除整棵树遇到最小的最大权是多少。 第一次以后的删除只能删除已被删除节点的邻居。
想要使答案尽量的小则优先选择权大的删除。 考虑到一个节点最多只能+2，假设ai最大值为mx，则答案可能为mx , mx +1 , mx +2。 而权为mx-1的节点最大权值可以达到mx+1，同样可以影响答案。
答案为mx的时候一定只有一个权为mx的节点 ， 如果有多个则后面删除的初始权为mx的节点的权一定会改变 。 如果有权mx-1的节点则一定要与权为mx的节点相连，否则一定有权为mx-1的点权值+2。
接下来讨论答案为mx+1的情况，权为mx-1的节点可以创造的最大权值为mx+1所以可以忽略。权为mx的节点可以创造的最大价值为mx+2，所以研究关于权为mx的节点的限制条件。
若答案为mx+1，则每个权为mx的节点一定最多只+1了一次。 假设有x个权为mx的节点 则一定有1个节点与x-1个节点相连。 否则x个节点中一定有节点将会+2。
答案不为mx和mx+1时即答案为mx+2 然后对于每种情况做判断就行了
#include <iostream> #include <algorithm> #include <sstream> #include <string> #include <queue> #include <cstdio> #include <map> #include <set> #include <utility> #include <stack> #include <cstring> #include <cmath> #include <vector> using namespace std; #define pb push_back #define scand(n) scanf("%d",&n) #define scandd(n,m) scanf("%d%d",&n,&m) #define scanddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define scanlld(n) scanf("%lld",&n) #define scanlldd(n,m) scanf("%lld%lld",&n,&m) #define scanllddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define scans(str) scanf("%s",str) #define ans() printf("%d",ans) #define ansn() printf("%d\n",ans) #define anss() printf("%d ",ans) #define llans() printf("%lld",ans) #define llanss() printf("%lld ",ans) #define llansn() printf("%lld\n",ans) #define REP(i,n) for(int i=0;i<(n);++i) #define REA(i,qwe,ewr) for(int i=qwe;i<=ewr;++i) #define RER(i,qwe,ewr) for(int i=qwe;i>=ewr;--i) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define pii pair<int,int> typedef long long ll; const int mod = 1000000007; const double eps=1e-9; const int INF=0x3f3f3f3f; const int MAXN=300005; int a[MAXN]; vector<int>v[MAXN]; int ct1[MAXN],ct2[MAXN]; int main() { #ifdef LOCAL freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // LOCAL int n; scand(n); int mx =-1e9; for(int i=1;i<=n;++i){ scand(a[i]); mx = max(mx,a[i]); } for(int i=1;i<n;++i){ int a,b; scandd(a,b); v[a].pb(b); v[b].pb(a); } int cnt1=0,cnt2=0,id=-1; int m1=0,m2=0; for(int i=1;i<=n;++i) { if(a[i]==mx) { ct1[i]++; ++cnt1; for(int j=0;j<v[i].size();++j)ct1[ v[i][j] ]++; id = i; } else if (a[i] == mx-1) { ct2[i]++; ++cnt2; for(int j=0;j<v[i].size();++j)ct2[ v[i][j] ]++; } } for(int i=1;i<=n;++i) m1 = max(m1,ct1[i]) , m2 = max(m2,ct2[i]); if(cnt1==1&&ct2[id]==cnt2)printf("%d",mx); else if(cnt1==m1)printf("%d",mx+1); else printf("%d",mx+2); return 0; }