[传送门]
首先有个贪心的想法，从叶子到根的路径的值呈递增更优，也就是大的深度越浅越好，因为如果把一个小的值放在深度浅的节点，则这以下的叶子节点都会被这个小的值影响，那么就肯定有更优的解代替这个放法，那么当叶子确定一个值的时候，从它往上的节点的相对大小就可以被确定了。
因为叶子节点只有20个，往状压DP上想。
$f\left[s\right]$表示集合$s$中的叶子节点的值已被确定的最大烦恼值，那么可以往下一个状态、比$s$多了一个叶子的$s‘$转移，$s‘$被确定的值，在多的那个叶子要放的值就是$s$状态下可以确定值的节点的个数+1。一条链上的点不需要用到，建个虚树就行了。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; const int MOD = 1e9 + 7; int n, m; struct E { int v, ne; } e[N << 1]; int cnt, in[N], leaf[N], sz[N], v[N], b[N]; int w[N], g[1 << 20], sum, tol; double f[1 << 20]; inline void add(int head[], int u, int v) { e[++cnt].v = v; e[cnt].ne = head[u]; head[u] = cnt; } int head[N], Head[N]; void dfs(int u, int last, int fa) { sum++; if (in[u] != 2) { b[++tol] = u; w[tol] = sum; sum = 0; if (u != fa) add(Head, fa, u), fa = u; } for (int i = head[u]; i; i = e[i].ne) { int v = e[i].v; if (v != last) dfs(v, u, fa); } } int main() { scanf("%d", &n); for (int i = 1, u, v; i < n; i++) { scanf("%d%d", &u, &v); add(head, u, v); add(head, v, u); in[u]++; in[v]++; } in[1] = -1; dfs(1, 1, 1); for (int i = 2; i <= n; i++) if (in[i] == 1) leaf[++m] = i, sz[i] = 1; for (int i = tol; i; i--) for (int j = Head[b[i]]; j; j = e[j].ne) sz[b[i]] += sz[e[j].v]; int S = (1 << m) - 1; f[0] = g[0] = 1; for (int s = 0; s < S; s++) { for (int i = 1; i <= tol; i++) v[b[i]] = 0; for (int i = 1; i <= m; i++) if ((s >> (i - 1)) & 1) v[leaf[i]] = 1; int id = 1; for (int i = tol; i; i--) { for (int j = Head[b[i]]; j; j = e[j].ne) v[b[i]] += v[e[j].v]; if (v[b[i]] == sz[b[i]]) id += w[i]; } double temp = f[s] * id; for (int i = 1; i <= m; i++) if (!((s >> (i - 1)) & 1) && temp > f[1 << (i - 1) | s]) f[1 << (i - 1) | s] = temp, g[1 << (i - 1) | s] = 1LL * id * g[s] % MOD; } printf("%lld\n", g[S]); return 0; }
原文：https://www.cnblogs.com/Mrzdtz220/p/11664632.html
