计蒜客 NOIP模拟赛(一) D1T2

原题: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;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注