原题：

 

蒜头君有一棵有根树，树的每一边都有边权，蒜头君想知道任意两点间最短距离之和为多少。另外，由于各种原因，蒜头君的树的边的边权会发生若干次改变，蒜头君想让你告诉他，每一次改变后，任意两点间最短距离之和为多少？

输入格式

第一行一个正整数 n，表示蒜头君的树上的结点个数。

接下来 n−1 行，每行两个正整数x​i​​,y​i​​， x​i​​表示i+1 号结点的父亲结点的编号，保证其父结点编号小于自己编号。y​i​​ 表示 i+1 号结点的父亲结点与自己间边的距离。

接下来一行一个整数 m，表示树的边权发生改变的次数。

接下来 m 行，每行两个正整数 a,b，表示将 a结点与其父亲结点之间的距离改为b，保证 a≥2。

输出格式

先输出一个整数，表示对于原始的树任意两点间最短距离之和。

接下来 m 行，每行输出一个整数，表示每一次改变后，任意两点间最短距离之和。

数据规模

 

样例输入

4

1 1

1 1

1 1

1

2 2

样例输出

9

12

 

开始在想LCA啥的［某个人气急败坏的要树剖］但是肯定TLE

虽然研究了一道类似的题解

但最后还是自己写出来了［类似的→hdu2376］

就是给一棵树然后求任意两点的最短距离之和。然后给m次修改重新求和。

方法是每一条边的两段的节点个数相乘［乘法原理］然后再乘上边权。就是计算每条边被经过的次数。

中间的逻辑一定要推理明白。这道题出题人还是很良心的。每次给的都是这条边底下的节点，对于计算方便很多。

m次修改就很好计算了。将这条边的边权修改，把原来的减去再加上现在的即可。

这题因为写反了一个循环所以爆零了。好忧伤。

但是只有经历了爆零才能重获新生吧。

不想多说了。上代码hhhhh。

#include
    
     #include
     
      #include
      
       using namespace std;int fa[100000];long long sum[100000],bian[100000];int main(){int n,m,j,i,k,w,e,s;long long ans;scanf("%d",&n);for(i=2;i<=n;i++){scanf("%d%lld",&fa[i],&bian[i]);sum[i]=1;}for(i=n;i>=2;i--)//这个循环要是逆序因为前面的要依赖后面的{sum[fa[i]]+=sum[i];}ans=0;for(i=1;i<=n;i++){ans+=bian[i]*sum[i]*(n-sum[i]);}printf("%lld\n",ans);scanf("%d",&m);for(i=0;i