TopCoder SRM 712 Div1 Medium AverageVarianceSubtree

誤差がきつすぎる。
https://community.topcoder.com/stat?c=problem_statement&pm=14570

問題

木を成すグラフが与えられる。
各頂点vには重さW[v]が設定されている。

グラフの空でない部分木における重さW[v]の分散の期待値を答えよ。

解法

グラフを根付き木とみなし、各頂点vを部分木の根とするような部分木の分散の総和を求めていこう。
分散は値の二乗の平均から平均値の二乗をいたものである。
よって、値の二乗和・値の和の二乗・要素数を求められるよう、以下の4つを木DPで求めていく。
A(v,n) := vを部分木の根とするような部分木のうちn頂点のものの組み合わせ
B(v,n) := vを部分木の根とするような部分木のうちn頂点のもののW[v]の総和
C(v,n) := vを部分木の根とするような部分木のうちn頂点のもののW[v]の二乗和
D(v,n) := vを部分木の根とするような部分木のうちn頂点のもののW[v]の和の二乗和

あとはsum(C(v,n)/n - D(v,n)/n^2)/sum(A(v,n))を求めればよい。

ただ、この問題は登場する値が大きく、そのような値の３乗程度の値の差を取ったりするため、long doubleを用いても誤差でWAする。
一つの解法として、先に全要素の値を平均値で引いておくという手があるようだ。
全体の分散が小さいときはこれで登場する値が小さくなるし、大きいときは解が大きな値になるので細かい誤差が気にならなくなる。

int N;
vector<int> E[101];
long double W[101];

long double num[51][51];
long double sum[51][51];
long double sum2[51][51];
long double sum3[51][51];

class AverageVarianceSubtree {
	public:
	
	int dfs(int cur,int pre,int ng) {
		
		num[cur][1]=1;
		sum[cur][1]=W[cur];
		sum2[cur][1]=sum3[cur][1]=W[cur]*W[cur];
		
		int i;
		int C=1;
		
		FORR(r,E[cur]) if(r!=pre && r>ng) {
			int TC=dfs(r,cur,ng);
			long double tnum[52]={};
			long double tsum[52]={};
			long double tsum2[52]={};
			long double tsum3[52]={};
			
			for(int c=1;c<=C+TC;c++) {
				for(int L=1;L<=C;L++) {
					int R=c-L;
					if(R<0 || R>TC) continue;
					tsum2[c]+=sum2[cur][L]*num[r][R]+2*sum[cur][L]*sum[r][R]+sum2[r][R]*num[cur][L];
					tsum[c]+=num[cur][L]*sum[r][R]+num[r][R]*sum[cur][L];
					tsum3[c]+=num[cur][L]*sum3[r][R]+num[r][R]*sum3[cur][L];
					tnum[c]+=num[cur][L]*num[r][R];
				}
			}
			C+=TC;
			FOR(i,C+1) {
				num[cur][i]=tnum[i];
				sum[cur][i]=tsum[i];
				sum2[cur][i]=tsum2[i];
				sum3[cur][i]=tsum3[i];
			}
		}
		num[cur][0]=1;
		
		return C;
	}
	
	
	double average(vector <int> p, vector <int> weight) {
		N=weight.size();
		int i,j;
		long double t=0;
		FOR(i,N) {
			E[i].clear();
			W[i]=weight[i];
			t+=W[i];
		}
		t /= N;
		FOR(i,N) W[i] -= t;
		
		FOR(i,N-1) {
			E[i+1].push_back(p[i]);
			E[p[i]].push_back(i+1);
		}
		
		ZERO(num);
		ZERO(sum);
		ZERO(sum2);
		ZERO(sum3);
		
		long double tnum=0;
		long double tot=0;
		FOR(i,N) {
			dfs(i,i,i);
			
			for(j=1;j<=50;j++) {
				tnum+=num[i][j];
				tot += sum3[i][j]/j - sum2[i][j]/j/j;
			}
		}
		
		return tot/tnum;
	}
}

まとめ

自分を含め多くの人が誤差問題を除けば解けていたと思われる問題。
コメントなどにあるように、期待値ではなく総和を答えるようにすればよかったのにね。