题目描述：
给你一个有\(n\)个点的树。当每一个点的度不超过\(4\)时这棵树是合法的。现在让你再添加一个点，在树仍然合法的情况下，一共有多少种树。
当两棵树同构时视作同一种。
保证输入的树是合法的。
数据范围：
\(1\leq n\leq 10^5\)
\(1\leq u_i,v_i\leq n\)
思路：
我们分析一下题目，会发现一件事情：如果我们令每个点为根的树的形态为 \(T_i\)，则如果 \(\exists (i,j),T_i=T_j\)，则在 \(i\) 和 \(j\) 上加点后的树的形态肯定还是相同的。
所以这个问题就转换为了以 \(n\) 个点为根，有多少种不同构的树。
这个问题显然我们可以使用 记忆化搜索+树Hash 来解决。
然后把所有 \(Hash\) 值扔到一个 \(set\) 里面就可以了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls i<<1
#define rs i<<1|1
#define pb push_back
#define pt putchar
#define All(a) a.begin(),a.end()
#define T int t;cin>>t;while(t--)
#define rand RAND
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=1e5+5;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
map<vector<int>,int>Hash;
map<int,int>mp[maxn];
int n;
vector<int>G[maxn];
int idx,deg[maxn];
int dfs(int u,int f){
if(mp[u][f])return mp[u][f];
vector<int>a;
for(int v:G[u]){
if(v==f)continue;
a.pb(dfs(v,u));
}
sort(All(a));
if(!Hash[a])Hash[a]=++idx;
return mp[u][f]=Hash[a];
}
signed main(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
G[u].pb(v);
G[v].pb(u);
deg[u]++;
deg[v]++;
}
set<int>s;
for(int i=1;i<=n;i++){
if(deg[i]<4){
s.insert(dfs(i,0));
}
}
cout<<s.size()<<endl;
return 0;
}