Contest3184 - 2021级新生个人训练赛第40场_H: Fennec VS. Snuke
//
#include<bits/stdc++.h>
using namespace std;const int N=1e5+6;vector<int> v[N];
int used[N];
int n,p;int find_p( int x,int len )
{int mid; used[x]=1;if( x==n ){mid=len/2+1+len%2;if( mid==len ) p=x; // x==n 此时 x==2 || x==3return mid;}for( auto i:v[x] ){if( used[i]==0 ){mid=find_p( i,len+1 );if( mid && mid==len && p==0 ) p=x; // mid==pos_p -> mid==len && x ~ len -> p=x if( mid ) return mid; // mid==0 死路}}return 0; // 死路
}int dfs( int x )
{int ans=1; used[x]=1;if( x==p ) return 0;for( auto i:v[x] ){if( used[i]==0 ) ans+=dfs( i );}return ans; // + 当前点x // ans=0 return ans+1
}int main()
{int i,x,y,ans;while( ~scanf("%d",&n) ){for( i=1;i<n;i++ ) // n points // n-1 edges{scanf("%d%d",&x,&y);v[x].push_back(y);v[y].push_back(x);}memset( used,0,sizeof( used ) );find_p( 1,1 );memset( used,0,sizeof( used ) );ans=dfs( 1 );printf( ans>n-ans ? "Fennec\n" : "Snuke\n" ); // ? true}return 0;
}