解析
这题思路挺秒啊.
本麻瓜终于找了道好题了(还成功把ztlztl大仙拖下水了)
看到叶子节点数<=20就应该是状压啊.
然而DP要怎么写啊?
首先,考虑到编号肯定是从下往上一次增大的,
另外,对于没有分支的一条链,它的编号应该是连续的.
并且一种类似于贪心的想法就是一个点(u)被编号时它的子树一定被编号完了.
所以这也像是一个类似于拓扑序的东西.
先建一棵虚树(因为叶子节点只有20有很多没用的点),边权设为这条链上不在虚树上的点数.
设状态(i)表示状压后集合(i)中的点的编号已经确定了.
那么我们可以把所有已经编号了的点数(cnt)求出来,
然后枚举没在点集中的叶子节点,它的编号就应该是(cnt+1),再更新答案就行了.
因为取模后无法比较大小所以我们可以另外开一个(double)数组来比较.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long
#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;
inline int read(){
int sum=0,f=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return f*sum;
}
const int N=100005;
const int M=(1<<20)+5;
const int Mod=1000000007;
struct edge{int to,next,w;}e[N<<1];
struct node{int size,dep,fa,son,top,dfn,is;}a[N];
int n;
int head[N],cnt=0,tp;
int q[N],sta[N],tot,top;
int f[M],s[N];double dp[M];
int que[N],qq[N],tt;
inline void add(int x,int y,int w){
e[++cnt]=(edge){head[x],y,w-1};head[x]=cnt;
}
inline void dfs(int x,int fa){
a[x].dep++;a[x].fa=fa;
a[x].size=a[x].is=1;a[x].dfn=++tp;
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;if(k==fa) continue;
a[k].dep=a[x].dep+e[i].w;
dfs(k,x);a[x].size+=e[i].w+a[k].size;
if(a[k].size>a[a[x].son].size) a[x].son=k;
a[x].is=0;
}
}
inline void dfs2(int x,int top){
a[x].top=top;
if(a[x].son) dfs2(a[x].son,top);
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;
if(k==a[x].son||k==a[x].fa) continue;
dfs2(k,k);
}
}
inline int lca(int x,int y){
while(a[x].top!=a[y].top){
if(a[a[x].top].dep<a[a[y].top].dep) swap(x,y);
x=a[a[x].top].fa;
}
if(a[x].dep>a[y].dep) swap(x,y);
return x;
}//树剖求lca
inline bool cmp(int x,int y){return a[x].dfn<a[y].dfn;}
signed main(){
n=read();
for(int i=1;i<n;i++){int x=read(),y=read();add(x,y,1);add(y,x,1);}
dfs(1,0);dfs2(1,1);
for(int i=1;i<=n;i++) if(a[i].is) q[++tot]=i;
sort(q+1,q+tot+1,cmp);if(q[1]!=1) sta[++top]=1;
memset(head,0,sizeof(head));cnt=0;
//*******
for(int i=1;i<=tot;i++){
if(!top){sta[++top]=q[i];continue;}
int p=lca(sta[top],q[i]);
while(top>1&&a[sta[top-1]].dep>=a[p].dep)
{add(sta[top-1],sta[top],a[sta[top]].dep-a[sta[top-1]].dep);top--;}
if(sta[top]!=p) add(p,sta[top],a[sta[top]].dep-a[p].dep),sta[top]=p;
sta[++top]=q[i];
}
while(top>1) add(sta[top-1],sta[top],a[sta[top]].dep-a[sta[top-1]].dep),top--;
//*******建虚树
a[1].dep=0;dfs(1,0);int lim=1<<tot;
f[0]=dp[0]=1;
for(int i=0;i<lim;i++){
for(int j=1;j<=tot;j++) if((i&(1<<(j-1)))) s[q[j]]=1;
int ret=0,l=1,r=0;tt=0;
for(int j=1;j<=tot;j++) if(s[q[j]]) que[++r]=q[j];
while(l<=r){
int x=que[l];l++;qq[++tt]=x;
ret+=a[x].dep-a[a[x].fa].dep;
if(!a[x].fa) continue;qq[++tt]=a[x].fa;
s[a[x].fa]+=s[x]+a[x].dep-a[a[x].fa].dep-1;
if(s[a[x].fa]==a[a[x].fa].size-1) s[a[x].fa]++,que[++r]=a[x].fa;
}//像拓扑序一样统计数量
for(int i=1;i<=tt;i++) s[qq[i]]=0;//清空s数组(之前用memsetT得一脸懵逼)
ret++;
for(int j=1;j<=tot;j++){
if((i&(1<<(j-1)))) continue;
int k=i|(1<<(j-1));
if(dp[k]<dp[i]*ret) f[k]=f[i]*ret%Mod,dp[k]=dp[i]*ret;
}
}
printf("%lld
",f[lim-1]);
return 0;
}