JSTSC DAY1 T2 已经弃疗
但也不能一直颓一个晚上。
那么我们来找点事情做。
这题看起来不错，过了这么长时间有10000000人过了。一定是道水题。题面上还有d(x,y)这么熟悉的距离，还是棵树。好了就是你了。
0.5小时后：这样应该差不多了。
0.75小时(WA*n)后：日。
1小时(AC)：呵呵。
题意：
n个点，n-1条边的树，有边权值。
任意选出三个点建城市，其花费是dis（a,b）+ dis（a,c）+ dis(b,c);
有q个询问，每次改变一条边的长度，求出所有建城市的方案的花费期望。
思路：
这题与罗爷爷在某场BC中绝杀的T3差不多(%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%）。取点的方案有C(n,3 )。
考虑每条边对结果的贡献。
假设我们有这样一棵树。
我们将其剖分。
剖出来x个点。
那么它对答案有多少贡献？我不会算。
不过我们可以猜出大概是这样一个东西：经过的次数=(x*(x-1)*y+y*(y-1)*x)*c
c是什么？一个常数。是多少？我不知道。
给你样例干嘛？让你凑的。常数就那几个，你1，*2/2*4/4*6/6 /c(n,3)都试试。
试出来是1/c(n,3)。
那么我们就可以做了。
答案怎么算都告诉你了代码就不贴了。
