题意：给定一棵n个点的树，问删去某个点之后所有的树同构，这样分割出来的树最多能有几棵
n<=4000
思路：分割成至少两个size相等的联通块之后size必定小于n/2，与树的重心的定义相同
预处理出重心（0，1或2个）之后上无根树同构板子
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef pair<ll,ll>P;
#define N 200010
#define M 1000000
#define INF 1e9
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1
#define fors(i) for(auto i:e[x]) if(i!=p) const int MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int dx[]={-,,,};
int dy[]={,,-,}; int head[N],vet[N],nxt[N],sz[N],mx[N],d[N],tot,Size,root; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} ll readll()
{
ll v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} void add(int a,int b)
{
nxt[++tot]=head[a];
vet[tot]=b;
head[a]=tot;
} void dfs1(int u,int fa)
{
int e=head[u];
sz[u]=,mx[u]=;
while(e)
{
int v=vet[e];
if(v!=fa)
{
dfs1(v,u);
sz[u]+=sz[v];
mx[u]=max(mx[u],sz[v]);
}
e=nxt[e];
}
} int ra[N]; int pw(int x,int y)
{
int res=;
while(y)
{
if(y&) res=1ll*res*x%MOD;
x=1ll*x*x%MOD;
y>>=;
}
return res;
} int inv(int x)
{
return pw(x,MOD-);
} struct Sub
{
VI S;
int d1,d2,H1,H2;
Sub(){d1=d2=; S.clear();} void add(int d,int v)
{
S.pb(v);
if(d>d1) d2=d1,d1=d;
else if(d>d2) d2=d;
} int Hash()
{
H1=H2=;
for(int i:S)
{
H1=1ll*H1*(ra[d1]+i)%MOD;
H2=1ll*H2*(ra[d2]+i)%MOD;
}
return H1;
} PII del(int d,int v)
{
if(d==d1) return {d2+,1ll*H2*inv(ra[d2]+v)%MOD};
return {d1+,1ll*H1*inv(ra[d1]+v)%MOD};
}
}; PII U[N];
int n,i,x,y,A[N];
Sub T[N]; void prepare(int n)
{
rep(i,,n) ra[i]=rand()%MOD;
} void dfsD(int u,int p)
{
Size++;
T[u]=Sub();
int e=head[u];
while(e)
{
int v=vet[e];
if(v!=p)
{
dfsD(v,u);
T[u].add(T[v].d1+,T[v].H1);
}
e=nxt[e];
}
T[u].Hash();
} void dfsU(int u,int p)
{
if(p!=root) T[u].add(U[u].fi,U[u].se);
A[u]=T[u].Hash();
int e=head[u];
while(e)
{
int v=vet[e];
if(v!=p)
{
U[v]=T[u].del(T[v].d1+,T[v].H1);
dfsU(v,u);
}
e=nxt[e];
}
} int isok(int root,int block)
{
int t[],c[];
int s=;
int e=head[root];
while(e)
{
int v=vet[e];
rep(i,,n) A[i]=;
Size=;
dfsD(v,root);
dfsU(v,root);
if(Size!=block) return ;
s++;
if(s==)
{
sort(A+,A+n+);
rep(i,,n) c[i]=A[i];
}
else
{
sort(A+,A+n+);
rep(i,,n)
if(A[i]!=c[i]) return ;
}
e=nxt[e];
}
return ;
} int main()
{
VI r;
srand();
prepare();
n=read();
rep(i,,n) head[i]=d[i]=;
tot=;
rep(i,,n-)
{
int x=read(),y=read();
add(x,y);
add(y,x);
d[x]++; d[y]++;
}
dfs1(,); r.clear(); rep(i,,n)
if(d[i]>=&&max(mx[i],n-sz[i])<=n/) r.pb(i); int ans=;
for(int i=;i<r.size();i++)
{
root=r[i];
if(isok(r[i],mx[r[i]])) ans=max(ans,d[r[i]]);
}
if(ans==) printf("-1\n");
else printf("%d\n",ans);
return ;
}