题目链接https://codeforces.com/contest/1252/problem/F
题意
给出一棵树，问删去一个度大于1的节点，使得剩下的树两两同构。问剩下的树最多是多少。
题解
容易想到，能够删去的点不可能存在多个，而且删去的必然是树的重心。剩下就是个判树同构了，而这个可以直接对树进行哈希来判断。
关于树的哈希与判树同构：https://www.luogu.org/problemnew/solution/P5043
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const ll N
=4e3+7;
const ll M
=(ll
)1e17+7;
const ll mod
=998244353;
struct Edge
{
ll v
,nxt
;
}e
[N
*2];
int p
[N
],edn
;
void add(ll u
,ll v
){
e
[++edn
]=(Edge
){v
,p
[u
]};p
[u
]=edn
;
e
[++edn
]=(Edge
){u
,p
[v
]};p
[v
]=edn
;
}
ll n
;
ll sz
[N
];
void getsz(ll x
,ll pre
){
sz
[x
]=1;
for(ll i
=p
[x
];i
!=-1;i
=e
[i
].nxt
)
if(e
[i
].v
!=pre
){
getsz(e
[i
].v
,x
);
sz
[x
]+=sz
[e
[i
].v
];
}
}
ll
getrt(ll x
,ll pre
){
for(ll i
=p
[x
];i
!=-1;i
=e
[i
].nxt
)
if(e
[i
].v
!=pre
){
if (sz
[e
[i
].v
]>n
/2) return getrt(e
[i
].v
,x
);
}
return x
;
}
ll a
[N
],tot
,rt
;
void getp(ll u
,ll f
){
a
[++tot
]=u
;
for(ll i
=p
[u
];~i
;i
=e
[i
].nxt
){
ll v
=e
[i
].v
;
if(v
==f
) continue;
getp(v
,u
);
}
}
;
ll
Hash(ll x
,ll f
){
vector
<int>q
;
int ans
=N
;
for(int i
=p
[x
];~i
;i
=e
[i
].nxt
)
if(e
[i
].v
!=f
&&e
[i
].v
!=rt
) q
.push_back(Hash(e
[i
].v
,x
));
sort(q
.begin(),q
.end());
for(int i
=0;i
<q
.size();i
++) ans
=(ans
*19260817+q
[i
])%mod
;
return (ans
*19260817+N
+1)%mod
;
}
ll ans
[N
][N
];
int main()
{
scanf("%lld",&n
);
for(ll i
=1;i
<=n
;i
++) p
[i
]=-1;edn
=-1;
for(ll i
=1,u
,v
;i
<n
;i
++){
scanf("%lld%lld",&u
,&v
);
add(u
,v
);
}
getsz(1,0);
rt
=getrt(1,0);
getsz(rt
,0);
ll num
=0;
for(ll i
=p
[rt
];~i
;i
=e
[i
].nxt
){
num
++;
tot
=0;
getp(e
[i
].v
,rt
);
for(ll j
=1;j
<=tot
;j
++) ans
[num
][j
]=Hash(a
[j
],0);
sort(ans
[num
]+1,ans
[num
]+tot
+1);
if(num
==1) continue;
ll k
=0;
while(k
<=tot
) if(ans
[num
][++k
]!=ans
[1][k
]) break;
if(k
<=tot
){printf("-1\n");return 0;}
}
printf("%lld\n",num
);
}
