Good Bye 2014 D. New Year Santa Network

題目鏈接:http://codeforces.com/contest/500/problem/D

題意

給定一棵含有n個節點的樹,每條邊有一個權值w_i
求任意三個點(c_i,c_j,c_k)之間的距離dis(c_i,c_j)+dis(c_i,c_k)+dis(c_j+c_k)的和的期望值
有m次操作,每次改變一條邊的權值,輸出每次改變之後的結果

解法

首先統計出來每條邊經過的次數
設edge_i將樹分為兩棵子樹分別A和B,兩棵子樹的大小分別為X和Y
先從A中取兩個點從B中取一個點,由於B中的一個點要到A中的兩個點去
所以經過edge_i這條邊的次數為C(X,2)*Y*2
同理在B中選兩個點在A中選一個點經過edge_i的次數為C(Y,2)*X
統計出來每條邊經過的次數count_i那麼期望就非常簡單了

class Cf500D {
    static final int N=100005;
    static class Nodes {
        int to;
        int id;
        Nodes(){}
        Nodes(int to,int id) {
            this.to=to;
            this.id=id;
        }
    }
    ArrayList<ArrayList<Nodes>> g=new ArrayList<ArrayList<Nodes>>();
    int[] from=new int[N];
    int[] to=new int[N];
    double[] cost=new double[N];
    int[] sz=new int[N];
    double[] count=new double[N];
    double ans;
    int n;
    void dfs(int f,int u) {
        ArrayList<Nodes> tmp=g.get(u);
        sz[u]=1;
        for(Nodes v:tmp) {
            int to=v.to;
            if(to==f) continue;
            int id=v.id;
            dfs(u,to);
            sz[u]+=sz[to];
            double s1=sz[to];
            double s2=n-sz[to];
            count[id]=s1*s2*(s2-1)+s2*s1*(s1-1);
        }
    }
    public void solve(int testNumber, Scanner in, PrintWriter out) {
        ans=0;
        n=in.nextInt();
        for(int i=0;i<=n;i++) {
            g.add(new ArrayList<Nodes>());
        }
        for(int i=1;i<n;i++) {
            from[i]=in.nextInt();
            to[i]=in.nextInt();
            cost[i]=in.nextDouble();
            g.get(from[i]).add(new Nodes(to[i],i));
            g.get(to[i]).add(new Nodes(from[i],i));
        }
        dfs(0,1);
        double p=n*1.0*(n-1)*(n-2)/6.0;
        for(int i=1;i<n;i++) {
            ans+=count[i]*cost[i];
        }
        int m=in.nextInt();
        for(int c=0;c<m;c++) {
            int id=in.nextInt();
            ans-=count[id]*cost[id];
            cost[id]=in.nextDouble();
            ans+=count[id]*cost[id];
            out.println(ans/p);
        }
    }
}