计蒜客NOIP模拟D1T2
原题：
蒜头君有一棵有根树，树的每一边都有边权，蒜头君想知道任意两点间最短距离之和为多少。另外，由于各种原因，蒜头君的树的边的边权会发生若干次改变，蒜头君想让你告诉他，每一次改变后，任意两点间最短距离之和为多少？
输入格式
第一行一个正整数 n，表示蒜头君的树上的结点个数。
接下来 n−1 行，每行两个正整数xi,yi， xi表示i+1 号结点的父亲结点的编号，保证其父结点编号小于自己编号。yi 表示 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<cstdio> #include<algorithm> #include<cstring> 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<m;i++) { scanf("%d%d",&j,&k);ans-=bian[j]*sum[j]*(n-sum[j]); bian[j]=k; ans+=bian[j]*sum[j]*(n-sum[j]); printf("%lld\n",ans); } return 0; }
转载于:https://www.cnblogs.com/hanyuweining/p/10321989.html
总结
以上是生活随笔为你收集整理的计蒜客NOIP模拟D1T2的全部内容，希望文章能够帮你解决所遇到的问题。
