题目概述

有一棵树，现在要给这棵树重编号，叶子节点的权值为到根路径的最小值，现在求叶子节点权值的积的最大值，保证叶子节点的个数不超过 $20$ 。

解题报告

可以想到这样的贪心：一个点的新编号肯定是子树中编号的最大值，否则肯定不优。

因为叶子个数不超过 $20$ ，对于一个叶子的确定状态，我们可以得出已经确定的点的个数（一个点所有儿子确定了他就确定了），那么下一个叶子肯定就放已经确定的点的个数 $+1$ 。

但是要怎么求出来呢？我们可以直接从叶子开始模拟一遍，但是复杂度爆炸。

因为是从叶子开始的，所以建出叶子的虚树就可以了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;typedef long double DB;
const int maxn=100000,Log=17,maxl=20,maxm=40,MOD=1e9+7;

int n,ti,Lt[maxn+5],Rt[maxn+5],dep[maxn+5],ST[maxn+5][Log+5],A[maxl+5],a[maxm+5],top,stk[maxm+5];
int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5],w[(maxn<<1)+5];
int len[maxn+5],tot[maxn+5],now[maxn+5],val[1<<maxl],f[1<<maxl];DB F[1<<maxl];

inline void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
inline void Add(int x,int y,int z) {son[++E]=y;w[E]=z;nxt[E]=lnk[x];lnk[x]=E;}
void Dfs(int x,int pre=0){
    Lt[x]=++ti;dep[x]=dep[pre]+1;ST[x][0]=pre;for (int j=1;j<=Log;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);Rt[x]=ti;if (Lt[x]==Rt[x]) A[++A[0]]=x,a[++a[0]]=x;
}
void VT(int x) {for (int j=lnk[x];j;j=nxt[j]) tot[x]++,len[son[j]]=w[j],ST[son[j]][0]=x,VT(son[j]);}
inline int LCA(int x,int y){if (dep[x]<dep[y]) swap(x,y);
    for (int j=Log;dep[x]>dep[y]&&~j;j--) {if (dep[ST[x][j]]>=dep[y]) x=ST[x][j];}if (x==y) return x;
    for (int j=Log;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];return ST[x][0];
}
inline bool cmp(const int &a,const int &b) {return Lt[a]<Lt[b];}
#define Son(x,y) (Lt[x]<=Lt[y]&&Rt[y]<=Rt[x])
int Count(int x) {if (x==1) return 1;return len[x]+(++now[ST[x][0]]<tot[ST[x][0]]?0:Count(ST[x][0]));}
inline int Fix(int x,int y) {if (F[x]*(val[x]+1)>F[y]) F[y]=F[x]*(val[x]+1),f[y]=(LL)f[x]*(val[x]+1)%MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);Dfs(1);
    sort(a+1,a+1+a[0],cmp);for (int i=2,si=a[0];i<=si;i++) a[++a[0]]=LCA(a[i],a[i-1]);a[++a[0]]=1;
    sort(a+1,a+1+a[0],cmp);a[0]=unique(a+1,a+1+a[0])-a-1;E=0;memset(lnk,0,sizeof(lnk));
    for (int i=1;i<=a[0];i++){
        while (top&&!Son(stk[top],a[i])) top--;
        if (top) Add(stk[top],a[i],dep[a[i]]-dep[stk[top]]);stk[++top]=a[i];
    }VT(1);
    for (int i=0;i<(1<<A[0]);i++){
        for (int j=1;j<=a[0];j++) now[a[j]]=0;
        for (int j=1;j<=A[0];j++) if (i>>j-1&1) val[i]+=Count(A[j]);
    }f[0]=1;F[0]=1;
    for (int i=0;i<(1<<A[0])-1;i++) for (int j=0;j<A[0];j++) if (!(i>>j&1)) Fix(i,i|(1<<j));
    printf("%d\n",f[(1<<A[0])-1]);return 0;
}