codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include<bits/stdc++.h> using namespace std; #define pb push_back #define ll long long #define maxn 100005 #define fr(i,j,k) for(int i=j;i<k;i++) #define f(n) fr(i,0,n) #define f1(n) fr(i,1,n+1) #define ms(i) memset(i,0,sizeof(i)); #define F first #define S second const int mod = 1e9+7; vector<int>g[4005]; vector<int>s[4005]; int sz[4005]; int f[4005]; int mx[4005]; int lb[4005]; int n; int dfs(int now,int pre){ vector<int>v; for(auto i:g[now]){ if(i!=pre&&lb[i]==lb[now]){ v.pb(dfs(i,now)); } } sort(v.rbegin(),v.rend()); ll ret = 73; for(auto i:v){ ret *= 6171; ret += i; ret %= mod; } return ret; } void dfs3(int x){ for(auto i:g[x]){ if(~lb[i])continue; lb[i] = lb[x]; dfs3(i); } } bool check(int x){ set<int>st; f(n+1){ lb[i] = -1; } lb[x] = 0; int cnt = 0; for(auto i:g[x]){ cnt++; lb[i] = cnt; dfs3(i); } f1(n){ if(lb[i]==1){ st.insert(dfs(i,0)); } } set<int>al; f1(n){ if(lb[i]==1||lb[i]==0||al.count(lb[i]))continue; int ret = dfs(i,0); al.insert(lb[i]); if(!st.count(ret))return 0; } return 1; } int dfs1(int now,int pre){ int cnt = 1; for(auto i:g[now]){ if(i == pre)continue; s[now].pb(dfs1(i,now)); } for(auto i:s[now]){ cnt += i; } s[now].pb(n-cnt); sort(s[now].begin(),s[now].end()); return cnt; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; f(n-1){ int add1,add2; cin >> add1 >> add2; g[add1].pb(add2); g[add2].pb(add1); } dfs1(1,0); int ans = -1; f1(n){ if(s[i].size()>1&&s[i][0]==s[i].back()){ if(check(i)){ ans = max((int)g[i].size(),ans); } } } cout << ans << endl; }
Private
[
?
]
Run code
Submit