题目链接：https://nanti.jisuanke.com/t/16446
题意：
给你一棵有n个节点的树以及每条边的长度，输出树上节点之间的最短距离和。然后进行m次操作，每次操作更改一条边的长度，分别输出每次操作后树上节点之间的最短距离和。
题解：
最短距离和 = ∑（树上每一条边被最短路经过的次数 * 这条边的长度）
一个节点到它父节点的边被经过的次数 = 该节点以及它的子孙的节点个数 * 除了该节点和它子孙之外的所有节点总个数
每一个节点以及它子孙节点的个数总和用一遍dfs保存在num数组中，然后算出每个sum[i] = num[i] * (n - num[i])，就可以求出在没有进行任何操作时的最短距离和。
对于每一次操作将第a个节点到它父节点的边长由原来的len[a]改为b，则将原来的最短距离和dis改为dis + (b - len[a])并输出，同时将len[a]改为b即可。
预处理&计算操作前的最短距离和的复杂度为O(N)，m次询问复杂度O(M)，总复杂度为O(N+M)。
注：本题会爆int，Ctrl+R全换成long long。。。
AC Code：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 100005 using namespace std; int n,m;
long long dis=;
long long len[MAX_N];
long long num[MAX_N];
long long sum[MAX_N];
vector<int> edge[MAX_N]; void read()
{
memset(len,,sizeof(len));
cin>>n;
for(int i=;i<=n;i++)
{
int x,y;
cin>>x>>y;
edge[x].push_back(i);
len[i]=y;
}
} long long dfs(int now)
{
long long tot=;
for(int i=;i<edge[now].size();i++)
{
tot+=dfs(edge[now][i]);
}
num[now]=tot;
return tot;
} void cal_sum()
{
for(int i=;i<=n;i++)
{
sum[i]=num[i]*(n-num[i]);
}
} void cal_dis()
{
for(int i=;i<=n;i++)
{
dis+=sum[i]*len[i];
}
} void solve()
{
dfs();
cal_sum();
cal_dis();
cout<<dis<<endl;
cin>>m;
for(int i=;i<m;i++)
{
int a,b;
cin>>a>>b;
dis+=(b-len[a])*sum[a];
len[a]=b;
cout<<dis<<endl;
}
} int main()
{
read();
solve();
}