原题：https://nanti.jisuanke.com/t/16446
北京市八十中的cjr说（特别感谢cjr提供思路，我进行了一下整理）：考虑每条边对答案的贡献：每条边肯定是一个父亲节点与一个儿子节点相连，该边对答案的贡献是size[i]*(n-size[i])*w，其中i为儿子节点，size[i]为该边的儿子节点所对应的子树大小（包括该儿子节点），w[i]为边权，n为总节点数。可以这样做是利用了乘法原理。想象一下，假设一棵有根树，要计算从Node:n到其它所有节点的最短距离：
该边必然要使用1*(n-1)次，该边对答案的贡献就为1*(n-1)*w[i]了。
子树大小由dfs算得即可，因为这是有根树。如果是图的话就不能这么干了，因为两个节点之间不仅仅又1条路径，这时候多源最短路只能用floyd做了。时间复杂度为O(n^3)。
本题第一次计算任意两点间距离之和：初始化子树大小DFS复杂度O(n)，算每条边的贡献O(n)，更改边长复杂度O(1)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include<iostream> #include<list> using namespace std; int n,m; long long father[100005],w[100005]; list<int> children[100005]; long long treesize[100005]; void dfs(int node){//获得子树大小 if(children[node].size()==0){ treesize[node]=1; return; } long long tot=0; for(list<int>::iterator i=children[node].begin();i!=children[node].end();i++){ dfs(*i); tot+=treesize[*i]; } treesize[node]=tot+1; return; } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=2;i<=n;i++){ cin>>father[i]>>w[i]; children[father[i]].push_back(i); } dfs(1); long long tot=0; for(int i=2;i<=n;i++){ tot+=treesize[i]*(n-treesize[i])*w[i]; } cout<<tot<<endl; cin>>m; for(int i=1;i<=m;i++){ int a,b; cin>>a>>b; long long change=treesize[a]*(n-treesize[a])*(b-w[a]); tot+=change; cout<<tot<<endl; w[a]=b; } } |