codeforces 500D - New Year Santa Network （树形DP+组合数学）

题目地址：http://codeforces.com/contest/500/problem/D

这题是要先求出每条边出现的次数，然后除以总次数，这样期望就求出来了。先用树形DP求出每个边左右两端总共有多少个点，然后用组合数学公式就可以推出来了。

代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
int vis[110000];
int head[110000], cnt, n;
LL fx[110000], fy[110000], dp[110000], w[110000];
struct node {
        int u, v, w, id, next;
}edge[210000];
void add(int u, int v, LL w, int id)
{
        edge[cnt].v=v;
        edge[cnt].w=w;
        edge[cnt].id=id;
        edge[cnt].next=head[u];
        head[u]=cnt++;
}
void dfs(int u)
{
        dp[u]=1;
        vis[u]=1;
        for(int i=head[u]; i!=-1; i=edge[i].next) {
                int v=edge[i].v;
                if(vis[v]) continue ;
                dfs(v);
                //printf("---%.2f\n",ans);
                fx[edge[i].id]=dp[v];
                fy[edge[i].id]=n-dp[v];
                dp[u]+=dp[v];
        }
}
void init()
{
        memset(head,-1,sizeof(head));
        cnt=0;
        memset(vis,0,sizeof(vis));
}
int main()
{
        int i, j, u, v, m, k, t;
        scanf("%d",&n);
        init();
        for(i=0; i<n-1; i++) {
                scanf("%d%d%I64d",&u,&v,&w[i]);
                add(u,v,w[i],i);
                add(v,u,w[i],i);
        }
        dfs(1);
        double ans=0;
        for(i=0;i<n;i++){
                ans+=fx[i]*(fx[i]-1)*fy[i]*w[i]+fx[i]*(fy[i]-1)*fy[i]*w[i];
        }
        scanf("%d",&m);
        while(m--) {
                scanf("%d%d",&k,&t);
                k--;
                //printf("--%.3f\n",ans);
                ans-=fx[k]*(fx[k]-1)*fy[k]*(w[k]-t)+fx[k]*fy[k]*(fy[k]-1)*(w[k]-t);
                //printf("---%.3f\n",ans);
                w[k]=t;
                printf("%.9f\n",ans/n/(n-1)/(n-2)*6);
        }
        return 0;
}