给定一个n,求 n 个节点的树的最大团个数的期望。 最大团的定义是选出最多的点,使得任意两点之间都有边.c++代码.时间复杂度nlogn
时间: 2024-02-28 19:55:59 浏览: 23
我们可以使用树形DP来解决这个问题。设$f[u]$表示以节点$u$为根的子树中最大团的个数期望,$g[u]$表示以节点$u$为根的子树中不包含节点$u$的最大团的个数期望,$siz[u]$表示以节点$u$为根的子树大小。则有如下转移方程:
$$f[u] = g[u] + \frac{1}{2^{siz[u]-1}}$$
$$g[u] = \sum\limits_{v\in son[u]} \frac{f[v]}{1-\frac{1}{2^{siz[v]+1}}}$$
其中,$son[u]$表示节点$u$的子节点集合。
这个转移方程的含义是,节点$u$不在最大团中的概率为$g[u]$,所以节点$u$在最大团中的概率为$1-g[u]$。又因为节点$u$的子节点中只要有一个不在最大团中,那么节点$u$就不能在最大团中,所以节点$u$在最大团中的概率为子节点$u$的$f[v]$的乘积之和除以不满足要求的概率$1-\frac{1}{2^{siz[v]+1}}$的乘积之和。
最后,我们只需要计算$f[1]$就是答案。时间复杂度为$O(n\log n)$。
以下是代码实现:
```c++
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1005;
vector<int> G[MAXN];
int n, siz[MAXN];
double f[MAXN], g[MAXN], ans;
void dfs(int u, int fa) {
siz[u] = 1;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
f[u] += g[v];
}
f[u] += 1.0 / (1 << (siz[u] - 1));
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == fa) continue;
g[u] += f[v] / (1 - 1.0 / (1 << (siz[v] + 1)));
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
printf("%.10lf\n", f[1]);
return 0;
}
```