http://codeforces.com/contest/500/problem/D

https://blog.csdn.net/ShiAokai/article/details/42921885?locationNum=8&fps=1

 1 import java.util.ArrayList; 2 import java.util.Scanner; 3  4 public class Main { 5  6 static int n; 7 static long[] cnt = new long[(int) (1e5 + 50)]; 8 static ArrayList<Edge>[] road = new ArrayList[(int) (1e5 + 50)]; 9 10 static int dfs(int x, int fa) {11 int child = 1;12 for (int i = 0, c, y; i < road[x].size(); i++) {13 y = road[x].get(i).y;14 if (y == fa) continue;15 c = dfs(y, x);16 child += c;17 cnt[road[x].get(i).id] = 1L * c * (n - c);18  }19 return child;20  }21 22 public static void main(String[] args) {23 Scanner io = new Scanner(System.in);24 n = io.nextInt();25 for (int i = 0; i < road.length; i++) road[i] = new ArrayList<>();26 int[] len = new int[n + 1];27 28 for (int i = 1, x, y; i <= n - 1; i++) {29 x = io.nextInt();30 y = io.nextInt();31 len[i] = io.nextInt();32 road[x].add(new Edge(y, i));33 road[y].add(new Edge(x, i));34  }35 36 dfs(1, -1);37 double sum = 0;38 for (int i = 1; i <= n - 1; i++) sum += cnt[i] * len[i];39 int q = io.nextInt();40 for (int i = 0, id2, len2; i < q; i++) {41 id2 = io.nextInt();42 len2 = io.nextInt();43 sum -= cnt[id2] * (len[id2] - len2);44 len[id2] = len2;45 //什么时候检测到double就什么时候升double46 //（）会改变检测顺序，所以下面的1.0如果没有就会溢出47 System.out.println((sum * 6) / (1.0 * (n - 1) * n));48  }49  }50 51 static class Edge {52 int y, id;53 54 public Edge(int y, int id) {55 this.y = y;56 this.id = id;57  }58  }59 60 }