相关链接
题目传送门：https://community.topcoder.com/stat?c=problem_statement&pm=14568&rd=16881
题目大意
给定一棵$n(n \le 50)$个结点的树，每个点上有一个点权$a_i(a_i \le 10^9)$
让你从中随意选出一个连通子图，询问这个连通子图中的每一个点的权值组成的序列的方差的期望是多少
小数输出，最终误差不得大于$\frac{1}{10^9}$
解题报告
将方差的式子化一化，发现我们大概要维护$E(\sum{a_i^2})$和$E((\sum{a_i})^2)$
第一个可以直接维护
第二个那一坨，我们还是使用期望的线性将其拆开，分别维护即可
最后再做一个树$DP$，总的复杂度大概在$O(n^3)$
Code
long double 最后一个点被卡精度了，只能用__float128
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 59;
const int M = N << 1;
class AverageVarianceSubtree {
int n,E,head[N],nxt[M],to[M];
__float128 ans,tot,val[N],s1[N][N],s2[N][N],s3[N][N],cnt[N][N];
public:
double average(vector<int> p, vector<int> weight) {
E = 1; ans = tot = 0; memset(head,0,sizeof(head));
memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2));
memset(s3,0,sizeof(s3)); memset(cnt,0,sizeof(cnt));
n = weight.size();
for (int i=1;i<=n;i++) val[i] = weight[i - 1];
for (int i=0;i<n-1;i++) AddEdge(i + 2, p[i] + 1);
DFS(1, 1);
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
ans += (s2[i][j] - s3[i][j] / j) / j;
tot += cnt[i][j];
}
}
return ans / tot;
}
private:
inline void AddEdge(int u, int v) {
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
void DFS(int w, int f) {
cnt[w][0] = cnt[w][1] = 1;
s1[w][1] = val[w];
s2[w][1] = s3[w][1] = val[w] * val[w];
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
DFS(to[i], w);
for (int t=n;t;t--) {
for (int a=1,b;b=t-a,a<t;a++) {
s3[w][t] += s3[w][a] * cnt[to[i]][b] + s3[to[i]][b] * cnt[w][a] + 2 * s1[w][a] * s1[to[i]][b];
s1[w][t] += s1[w][a] * cnt[to[i]][b] + s1[to[i]][b] * cnt[w][a];
s2[w][t] += s2[w][a] * cnt[to[i]][b] + s2[to[i]][b] * cnt[w][a];
cnt[w][t] += cnt[w][a] * cnt[to[i]][b];
}
}
}
}
}
};