[USACO19JAN]Grass Plantin

本人水平有限，题解不到为处，请多多谅解

本蒟蒻谢谢大家观看

乍一看，用dfs遍历树在七搞八搞，最后怀着激动的心情提交，AC三个点，TLE七个点

30分代码：

 1 #include<bits/stdc++.h>
 2 #pragma GCC optimize(3)
 3 const int N=5e5+100;
 4 using namespace std;
 5 int n,tot,cnt=1,ans;
 6 int ver[N],head[N],nxt[N],f[N],vis[N];
 7 void inint(){
 8     freopen("grass.in","r",stdin);
 9     freopen("grass.out","w",stdout);
10 }
11 inline int read(){
12     int x=0,f=1;char ch=getchar();
13     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
14     while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
15     return x*f;
16 }
17 void add(int x,int y){
18     ++tot;
19     ver[tot]=y;
20     nxt[tot]=head[x];
21     head[x]=tot;
22 }
23 void dfs(int x,int fa){
24     f[x]=fa;
25     for(int i=head[x];i;i=nxt[i]){
26         int y=ver[i];
27         if(y!=fa){
28             f[y]=x;
29             dfs(y,x);
30         }
31     }
32 }
33 int main()
34 {
35     //inint();
36     n=read();    
37     memset(vis,1,sizeof(vis));
38     for(int i=1;i<n;i++){
39         int x,y;
40         x=read(),y=read();
41         add(x,y),add(y,x);
42     }    
43     dfs(1,0);
44     for(int i=1;i<=n;i++)vis[i]=1;
45     for(int i=1;i<=n;i++){
46         for(int j=1;j<=n;j++){
47             if(f[j]==i&&i!=j){
48                 if(vis[j]==vis[i]){
49                     vis[j]=vis[j]+1;
50                 }
51             }
52             if(f[i]==f[f[j]]&&i!=j){
53                 if(vis[i]==vis[f[j]]){
54                     vis[j]=vis[j]+1;
55                 }
56                 if(f[j]==i&&i!=j){
57                     if(vis[j]==vis[i]){
58                         vis[j]=vis[j]+1;
59                     }
60                 }            
61             }
62         }
63     }
64     for(int i=1;i<=n;i++)ans=max(ans,vis[i]);
65     printf("%d
",ans);
66     return 0;
67 }
68 /*
69 4
70 1 2
71 4 3
72 2 3
73 
74 7
75 1 2
76 1 3
77 2 4
78 2 5
79 3 6
80 3 7
81 */

仔细一想，这不就是统计树上点的度吗？

因为是无向图，所以入度==出度，直接类似于桶排，因为只要有需要统计的数出现，我们记一个num数组，num[i]++;可以统计该点的度。因为只要有点与该点连边，该点与连点就会出现在输入样例中，直接统计即可。

注意：最后答案要+1，因为自身初始时就已经有一种情况了。

code:

 1 #include<bits/stdc++.h>
 2 #pragma GCC optimize(3)
 3 const int N=5e5+100;
 4 using namespace std;
 5 int n,ans;
 6 int num[N];
 7 inline int read(){
 8     int x=0,f=1;char ch=getchar();
 9     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
10     while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
11     return x*f;
12 }
13 inline void write(int x){
14      char F[200];
15      int tmp=x>0?x:-x ;
16      if(x<0)putchar('-') ;
17      int cnt=0 ;
18         while(tmp>0)
19         {
20             F[cnt++]=tmp%10+'0';
21             tmp/=10;
22         }
23         while(cnt>0)putchar(F[--cnt]) ;
24 }
25 int main()
26 {
27     n=read();
28     for(int i=1,x,y;i<n;i++){
29         x=read(),y=read();
30         num[x]++,num[y]++;
31     }
32     for(int i=1;i<=n;i++){
33         ans=max(ans,num[i]);
34     }
35     printf("%d
",ans+1);
36     return 0;
37 }