这道题首先是要看看该如何化简，先把三元组化成二元组。
之后统计经过某条边的 次数$*$权值 的和。
最后除以总基数 $tot$
其中，每条边被计算的次数为 子树的点数$*$非子树的点数 （自己想想）
然后就没了。
ps:一定要注意$n$个节点的树有$n-1$条边，本宝宝调了一下午+一晚上。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct data{int v;int value;int nxt;}edge[200010]; int alist[100010];int cnt; void add(int u,int v,int value) { edge[++cnt].nxt=alist[u]; edge[cnt].v=v; edge[cnt].value=value; alist[u]=cnt; } int len[100010]; int num[100010]; int n,m; int in[100010];int out[100010]; double ans;double tot; void dfs(int x,int f) { num[x]=1; for(int i=alist[x];i!=-1;i=edge[i].nxt) { int v=edge[i].v; if(v==f) continue; dfs(v,x); num[x]+=num[v]; ans+=(double)edge[i].value*num[v]*(n-num[v])/tot; } } int u,v,value; int main() { scanf("%d",&n); memset(alist,-1,sizeof(alist)); for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&value); in[i]=u; out[i]=v; len[i]=value; add(u,v,value); add(v,u,value); } tot=(double)n*(n-1)/6.0; dfs(1,-1); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); value=min(num[in[u]],num[out[u]]); ans-=(double)(len[u]-v)*value*(n-value)/tot; len[u]=v; printf("%.8lf\n",ans); } return 0; }
