题面
题解
思路很好的一道题
zsq这个麻瓜总算找了几道好题做了
题目拿到手上, 首先考虑贪心, 要使答案更大, 则要使编号小的点对答案的贡献更小
那么将它放在深度更浅的地方肯定没有放在更深的地方更优
所以得到了一条贪心思路
- 编号较小的点放在深度较大的点上
所以, 对于某一个点, 只有当它子树中所有点都被确定了以后它的编号才会被确定
但是要考虑到每个叶节点先后填数对答案的影响
考虑到叶节点总数很小, 状压???
设(f[i])为状态为(i)时不同的叶节点乘积最大值, 考虑到这个东西会爆, 将乘变为取对数后加
这样, 我们重新设(f[i], g[i])分别为状态为(i)时, 最大乘积取模后的值, 每个叶节点取对数后和的最大值
比较的时候这样比就行了
if(g[tmp] < g[i] + x)
g[tmp] = g[i] + x, f[tmp] = 1ll * f[i] * (sum + 1) % mod;
然后把所有的只有一个子节点的点压到它的子节点中去
这不就是虚树吗
然后枚举一个状态的时候, 暴力将虚树中可以标号的点的个数算出来, 就可以知道下一个叶节点的编号是多少了
时间复杂度(O(2 ^ {20}) (*) 虚树点数()), 具体实现细节看代码
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define N 100005
#define mod 1000000007
using namespace std;
int n, cnt, tot, num[N], len[N], vis[N];
template < typename T >
inline T read()
{
T x = 0, w = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * w;
}
namespace Graph
{
int head[N];
struct edge { int to, next; } e[N << 1];
inline void adde(int u, int v) { e[++cnt] = (edge) { v, head[u] }; head[u] = cnt; }
};
using namespace :: Graph;
namespace ShuPou
{
int sz[N], fa[N], dep[N], son[N], top[N], dfn[N];
void dfs1(int u, int pre)
{
sz[u] = 1; fa[u] = pre; dep[u] = dep[pre] + 1; dfn[u] = ++cnt;
for(int i = head[u]; i; i = e[i].next)
{
int v = e[i].to; if(v == pre) continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v]) son[u] = v;
}
if(sz[u] == 1) num[++tot] = u;
}
void dfs2(int x, int y)
{
top[x] = y;
if(!son[x]) return; dfs2(son[x], y);
for(int i = head[x]; i; i = e[i].next)
if(e[i].to != fa[x] && e[i].to != son[x])
dfs2(e[i].to, e[i].to);
}
int LCA(int x, int y)
{
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
};
using namespace :: ShuPou;
namespace Xushu
{
int stk[N], topp;
bool cmp(int a, int b) { return dfn[a] < dfn[b]; }
void build()
{
sort(num + 1, num + tot + 1, cmp);
for(int i = 1; i <= tot; i++)
vis[num[i]] = i; //记录哪些点是叶节点
int x = tot; cnt = 0;
for(int i = 1; i <= x; i++)
{
if(i == x) { num[++tot] = 1; continue; }
int lca = LCA(num[i], num[i + 1]);
num[++tot] = lca;
}
sort(num + 1, num + tot + 1, cmp);
tot = unique(num + 1, num + tot + 1) - num - 1;
for(int i = 1; i <= tot; i++)
head[num[i]] = 0;
for(int i = 1; i <= tot; i++)
{
while(topp && dfn[num[i]] > dfn[stk[topp]] + sz[stk[topp]] - 1) topp--;
if(topp)
adde(stk[topp], num[i]), len[num[i]] = dep[num[i]] - dep[stk[topp]] - 1;
stk[++topp] = num[i];
}//这个如果有不会的左转百度吧
cnt = x;
}
};
using namespace :: Xushu;
namespace DP
{
int f[(1 << 20) + 5], v[N]; double g[(1 << 20) + 5];
void clear()
{
memset(f, 0, sizeof(f)); memset(g, -0x3f3f3f3f, sizeof(g));
f[0] = 1; g[0] = 0;
}
void dp()
{
clear();
int lim = (1 << cnt);
for(int i = 0; i < lim; i++)
{
int sum = 0;
for(int j = 1; j <= tot; j++)
v[num[j]] = 0; //清空上一种状态每个点对sum的贡献
for(int j = tot; j; j--)
{
v[num[j]] = 1; //对于所有点, 它可以选自己
if(vis[num[j]])
if(!(i >> (vis[num[j]] - 1) & 1))
v[num[j]] = 0; //若这个点是叶节点并且他不在这个状态中, 把它变成0(本来也就选不了)
for(int k = head[num[j]]; k; k = e[k].next)
v[num[j]] += v[e[k].to];//加上子节点贡献
if(v[num[j]] == sz[num[j]])//若整棵子树被选
sum += len[num[j]] + 1, v[num[j]] += len[num[j]];
//它对它父节点的贡献是它加上他到它父节点那一段包括它自己不包括它的父节点(也就是len[u])的长度加上它子树的大小
//它对sum的贡献是len[u] + 1, 因为他自己以前没有被子节点贡献过, 也就是这个点本来没有被计算过
//自己画个图理解一下就行了
}
for(int j = 1; j <= cnt; j++)
if(!((i >> (j - 1)) & 1))
{
int tmp = i | (1 << (j - 1));
double x = log(sum + 1);
if(g[tmp] < g[i] + x)
g[tmp] = g[i] + x, f[tmp] = 1ll * f[i] * (sum + 1) % mod;
}
}
}
};
using namespace :: DP;
int main()
{
n = read <int> ();
for(int i = 1; i < n; i++)
{
int u = read <int> (), v = read <int> ();
adde(u, v); adde(v, u);
}
cnt = 0; dfs1(1, 0); dfs2(1, 1); //树剖找LCA
build();//建虚树
dp();
printf("%d
", f[(1 << cnt) - 1]);
return 0;
}