Good Bye 2014 D--- New Year Santa Network

Consider the first sample. There are 6 triples: (1,?2,?3),?(1,?3,?2),?(2,?1,?3),?(2,?3,?1),?(3,?1,?2),?(3,?2,?1). Because n?=?3, the cost needed to build the network is always d(1,?2)?+?d(2,?3)?+?d(3,?1) for all the triples. So, the expected cost equals to d(1,?2)?+?d(2,?3)?+?d(3,?1).

好题，首先我们要求在没有修改的情况下，选三个点的期望代价，这个代价来自于边，所以我们要统计出每一条边的贡献值，最后除以Ｃ（３，ｎ）就是期望值

这个可以先树形ｄｐ预处理，然后每次修改边，就把期望值减去相差的那部分，就是答案了

/*************************************************************************
    > File Name: cf_d.cpp
    > Author: ALex
    > Mail: [email protected] 
    > Created Time: 2014年12月31日 星期三 09时16分18秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int num[N];
int par[N];
int head[N], tot;
__int64 n;
int a[N], b[N], l[N];
double ans;

struct node
{
	int weight;
	int next;
	int to;
}edge[N << 1];

void addedge(int from, int to,int weight)
{
	edge[tot].weight = weight;
	edge[tot].to = to;
	edge[tot].next = head[from];
	head[from] = tot++;
}

int dfs(int u, int fa)
{
	int child = 1;
	par[u] = fa;
	for (int i = head[u]; ~i; i = edge[i].next)
	{
		int v = edge[i].to;
		if (v == fa)
		{
			continue;
		}
		int num_v = dfs(v, u);
		double cnt = (double)((n - num_v) * (num_v - 1) * num_v * 1.0  / 2);
		cnt += (double)((n - num_v) * (n - num_v - 1) * num_v * 1.0 / 2);
		cnt *= 2;
		ans += cnt * edge[i].weight;
		child += num_v;
	}
	num[u] = child;
//	printf("node %d has %d\n", u, num[u]);
	return num[u];
}

int main()
{
	while (~scanf("%I64d", &n))
	{
		memset (num, 0, sizeof(num));
		ans = 0;
		tot = 0;
		memset (head, -1, sizeof(head));
		for (int i = 1; i <= n - 1; ++i)
		{
			scanf("%d%d%d", &a[i], &b[i], &l[i]);
			addedge(a[i], b[i], l[i]);
			addedge(b[i], a[i], l[i]);
		}
		dfs(1, -1);
		double cnt = (n - 1) * (n - 2) * n * 1.0 / 6;
		ans /= cnt;
		int q;
		int r, w;
		scanf("%d", &q);
		while (q--)
		{
			scanf("%d%d", &r, &w);
			int dis = l[r] - w;
			l[r] = w;
			int son;
			if (par[a[r]] == b[r])
			{
				son = a[r];
			}
			else
			{
				son = b[r];
			}
			double x = (double)(n - num[son]) * (num[son] - 1) * num[son] * 1.0/ 2;
			x += (double)(n - num[son] - 1) * (n - num[son]) * num[son] *1.0 / 2;
			x *= 2;
			x *= dis;
			x /= cnt;
			ans -= x;
			printf("%.10f\n", ans);
		}
	}
	return 0;
}