题意：就是一些银行互联，串成一串，并且n个银行有n-1个边，要把这些银行全部黑掉需要电脑的最低限度是多少，并且黑掉一个电脑邻居及次邻居值就会+1
思路：对于mx发生的情况，你必须保证所有银行只有一个mx，如果多于一个必然是不行的。那么对于只有一个mx，是否有可能结果比mx大呢？答案是肯定的，比如你又一堆mx-1的强度，他们有的与mx间接相连，那么k就变成了mx+1；因此在有一个mx的情况下，所有mx-1都与他直接连接，结果就是max，否则结果是mx+1；对于mx+1情况，除了上边以外，还有就是mx个数大于1，但是他们被同一个银行直接相连。其他情况为mx+2。
思考：当时就想着怎么遍历出来，想到了肯定会是分类，但是找到他并不是很容易的事
代码：
1 #include <iostream>
2 #include <set>
3 #include <vector>
4 #include <cstring>
5 #include <string>
6 #include <stdio.h>
7 #define maxn 300005
8 #define INF 0x3fffffff
9 using namespace std;
10 vector<int> a[maxn];
11 int s[maxn];
12 int n;
13 typedef long long LL;
14 void solve()
15 {
16 int i,mx,ans,num1,num2,num3,counter,k,j;
17 mx=-INF;
18 num1=num2=num3=0;
19 j=0;
20 for(i=1;i<=n;i++)
21 {
22 mx=max(mx,s[i]);
23 }
24 for(i=1;i<=n;i++)
25 {
26 if(s[i]==mx)
27 {
28 num1++;
29 k=i;
30 }
31 else if(s[i]==mx-1)num2++;
32 }
33 if(num1==1)
34 {
35 counter=0;
36 for(i=0;i<a[k].size();i++)
37 {
38 if(s[a[k][i]]==mx-1)counter++;
39 }
40 if(counter==num2)ans=mx;
41 else ans=mx+1;
42 }
43 else
44 {
45 int flag;
46 flag=0;
47 for(i=1;i<=n;i++)
48 {
49 counter=0;
50 for(j=0;j<a[i].size();j++)
51 {
52 int v;
53 v=a[i][j];
54 if(s[v]==mx)counter++;
55 }
56 if(s[i]==mx)counter++;
57 if(counter==num1)flag=1;
58 }
59 if(flag)ans=mx+1;
60 else ans=mx+2;
61 }
62 cout<<ans<<endl;
63 }
64 int main()
65 {
66 int i,start,end;
67 while(cin>>n)
68 {
69 memset(s,0,sizeof(s));
70 for(i=1;i<=n;i++)
71 {
72 cin>>s[i];
73 a[i].clear();
74 }
75 for(i=0;i<n-1;i++)
76 {
77 scanf("%d%d",&start,&end);
78 a[start].push_back(end);
79 a[end].push_back(start);
80 }
81 solve();
82 }
83 return 0;
84 }
View Code