直接按边分，2个点在边的一边，1个在另一边，组合出来就是这个边对答案的贡献，权值换了就再重新算个数而已。
1 #include <bits/stdc++.h> 2 #define LL long long 3 using namespace std; 4 inline int ra() 5 { 6 int x=0,f=1; char ch=getchar(); 7 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 8 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 9 return x*f; 10 } 11 LL n,m,cnt=1; 12 double ans,tot; 13 struct edge{ 14 int from,to,next; 15 LL v,T; 16 }e[200005]; 17 LL size[100005],head[100005],deep[100005]; 18 void insert(int x, int y, int v) 19 { 20 e[++cnt].next=head[x]; e[cnt].from=x; e[cnt].to=y; e[cnt].v=v; head[x]=cnt; 21 } 22 void dfs(int x, int fa) 23 { 24 size[x]=1; 25 for (int i=head[x];i;i=e[i].next) 26 { 27 if (e[i].to==fa) continue; 28 deep[e[i].to]=deep[x]+1; 29 dfs(e[i].to,x); 30 size[x]+=size[e[i].to]; 31 } 32 } 33 int main(int argc, char const *argv[]) 34 { 35 n=ra(); tot=n*(n-1)*(n-2)/6.0; 36 for (int i=1; i<n; i++) 37 { 38 int x=ra(),y=ra(),v=ra(); 39 insert(x,y,v); insert(y,x,v); 40 } 41 dfs(1,0); 42 for (int i=2; i<=cnt; i+=2) 43 { 44 int now=i/2,x=e[i].from,y=e[i].to; 45 if (deep[x]>deep[y]) swap(x,y); 46 LL s1=n-size[y],s2=size[y]; 47 e[i].T+=s1*s2*((LL)n-2); 48 ans+=e[i].T*e[i].v; 49 } 50 m=ra(); 51 for (int i=1; i<=m; i++) 52 { 53 int x=ra(),y=ra(); 54 LL now=x*2; 55 ans-=(e[now].v-y)*e[now].T; 56 e[now].v=y; 57 printf("%.10lf ",(double)ans/tot); 58 } 59 return 0; 60 }