链接：点击打开链接
题意：给定一颗有N个节点的带权树，之后进行M次操作：Q操作：询问树上所有点对之间的距离之和，E操作：修改树上某一条边的权值
代码：
#include <queue> #include <vector> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int siz=100005; struct node{ long long to,cost; }; vector<node> G[siz]; long long n,ans,dp[siz],dis[siz],val[siz]; void dfs(long long s,long long fa){ long long i,tmp; dp[s]=1; for(i=0;i<G[s].size();i++){ tmp=G[s][i].to; if(tmp==fa) continue; dis[tmp]=dis[s]+1; val[tmp]=G[s][i].cost; //把深度深的点设为边的编号 dfs(tmp,s); dp[s]+=dp[tmp]; ans+=(val[tmp]*(dp[tmp]*(n-dp[tmp]))); } } int main(){ //算每条边的贡献值，更新时直接根据 string s; //节点数更新 long long m,i,j,u,v,w; while(scanf("%lld%lld",&n,&m)!=EOF){ for(i=1;i<=n;i++) G[i].clear(); for(i=1;i<n;i++){ scanf("%lld%lld%lld",&u,&v,&w); G[u].push_back((node){v,w}); G[v].push_back((node){u,w}); } memset(dis,0,sizeof(dis)); memset(val,0,sizeof(val)); ans=0; dfs(1,0); while(m--){ cin>>s; if(s=="QUERY") printf("%lld\n",ans); else{ scanf("%lld%lld%lld",&u,&v,&w); if(dis[u]>dis[v]) swap(u,v); //直接根据子树点的个数更新 ans+=((w-val[v])*dp[v]*(n-dp[v])); val[v]=w; } } } return 0; }