首先考虑暴力 DP，设 \(f(i,v_1,v_2,now)\) 为已经将前 \(i\) 个数填入，\(i\) 填在 \(v_1\)，\(j\) 填在 \(v_2\) 点，已经填完点的状态是 \(now\)（状压一下存在一个 long long 里）的方案数。转移时直接枚举下一个点暴力转移，只需要保证新的点没有被访问过，并且填上新点后，\(v_1\) 的所有邻接点都被填上即可。
其实直接暴力转移，复杂度是对的。
我们考虑对于一个状态 \((i,v_1,v_2,now)\)，将 \(v_1\) 和 \(v_2\) 在树中剪掉，剩下的连通块（最多 \(7\) 个，因为每个点度数最多为 \(4\)）中，要么全被填了，要么都没被填。因为一个连通块内被填的点上的数一定小于等于 \(n-2\)，后面填的点一定和这些点的差一定大于 \(2\)，因此一定不合法。
状态数最多为 \(n^3 \times 2^7\)，复杂度 \(O(n^3 \times 2^7)\)。
注意特判 \(n=1\) 的情况。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
const int mod=1e9+7;
unordered_map<long long,int> mp[65][65][65];
vector<int> e[65];int n;
signed main(){
rd(n);
if(n==1){
printf("1\n");
return 0;
}
for(int i=1;i<n;i++){
int x,y;rd(x,y);
e[x].push_back(y);
e[y].push_back(x);
}
for(int v1=1;v1<=n;v1++)
for(int v2=1;v2<=n;v2++){
if(v1==v2)continue;
mp[2][v1][v2][(1ll<<v2)|(1ll<<v1)]+=1;
}
for(int i=2;i<n;i++){
for(int v1=1;v1<=n;v1++){
for(int v2=1;v2<=n;v2++){
if(v1==v2)continue;
long long bas=0;
for(int x:e[v1])bas|=(1ll<<x);
for(int x=1;x<=n;x++){
for(pair<long long,int> p:mp[i][v1][v2]){
if(p.first&(1ll<<x))continue;
if(((p.first|(1ll<<x))&bas)==bas){
(mp[i+1][v2][x][p.first|(1ll<<x)]+=mp[i][v1][v2][p.first])%=mod;
}
}
}
}
}
}
int ans=0;
for(int v1=1;v1<=n;v1++)
for(int v2=1;v2<=n;v2++){
if(v1==v2)continue;
for(auto p:mp[n-1][v1][v2])
(ans+=p.second)%=mod;
}
printf("%d\n",ans);
return 0;
}