CF718D题解
CF718D Andrew and Chemistry
题意
给你一个有 n 个点的树。当每一个点的度不超过 4 时这棵树是合法的。现在让你再添加一个点，在树仍然合法的情况下，一共有多少种树。
当两棵树同构时视作同一种。
保证输入的树是合法的。
思路
很显然，如果我们对于一个节点 A 再连接一个新的节点 B，如果以节点 A 作为根时哈希值与已经求出的其他节点哈希值相同，那么在 A 上连接一个 B 和在相同哈希值的节点上连接一个 B 显然是同构的，所以现在的问题转换为，对于原图中度数小于 4 的节点，让这些节点作为树的根求出的哈希值的值的数量。
于是这个问题成功地转换为树哈希模板题
看了一下其他题解的哈希做法，都是记忆化搜索做法，感觉没有我的优（毕竟去掉记忆化就是平方复杂度了），这里提供一种哈希方法，在线性复杂度内求出所有点的哈希值，使用了换根 DP。
哈希式子如下
至于换根的话看代码吧，比较简单。
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
inline int read()
{
int ret=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return ret;
}
const int maxn=1e5+10;
struct node
{
int v,next;
}e[maxn<<1];
int cnt,head[maxn];
int n;
void add(int u,int v)
{
e[++cnt].next=head[u];
e[cnt].v=v;
head[u]=cnt;
}
bool vis[maxn*15];
int p[maxn];
void prework(int n)
{
int tot=0;
for(int i=2;tot<=n;i++)
{
if(!vis[i]) p[++tot]=i;
for(int j=1;j<=tot && i*p[j]<=maxn*15;j++)
{
vis[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}
ull f[maxn];
int sz[maxn];
void dfs(int u,int fa)
{
sz[u]=f[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u);
f[u]+=f[v]*p[sz[v]];
sz[u]+=sz[v];
}
}
void dfs1(int u,int fa)
{
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
f[v]+=(f[u]-f[v]*p[sz[v]])*p[n-sz[v]];
dfs1(v,u);
}
}
int d[maxn];
set<ull> s;
int main()
{
n=read();
prework(n+1);
for(int i=1,x,y;i<n;i++)
{
x=read();y=read();
add(x,y);add(y,x);
d[x]+=1;d[y]+=1;
}
dfs(1,0);dfs1(1,0);
for(int i=1;i<=n;i++)
{
if(d[i]>=4) continue;
s.insert(f[i]);
}
cout<<s.size()<<endl;
return 0;
}注意这种方法需要使用筛法求质数，需要点数个质数，在预处理的时候控制好范围。