[JZOJ5776]【NOIP2008模拟】小x游世界树

╰半橙微兮° 2021-12-16 15:53 138阅读 0赞

#### Description ####

小x得到了一个(不可靠的)小道消息，传说中的神岛阿瓦隆在格陵兰海的某处,据说那里埋藏着亚瑟王的宝藏，这引起了小x的好奇，但当他想前往阿瓦隆时发现那里只有圣诞节时才能到达，然而现在已经春天了，不甘心的他将自己的目的地改成了世界树，他耗费了大量的时间，终于将自己传送到了世界树下。世界树是一棵非常巨大的树，它有着许许多多的枝条以及节点，每个节点上都有一个平台。好不容易来到传说中的世界树下，小x当然要爬上去看看风景。小x每经过一条边都会耗费体力值。然而世界树之主想给他弄（gáo）些（dǐan）麻（shì）烦（qíng），于是他在每条边上都设了一个魔法阵，当小x踏上那条边时会被传送回根节点，魔法阵只生效一次。这岂不是要累死小x？幸运的是，每个平台上都有无数个加速器，这些加速器可以让小x在当前节点所连的边上耗费的体力值减少，不同平台的加速器性能不一定相同，但同一个平台的加速器性能绝对相同。世界树之主给了小x一次“换根”的机会，他可以将世界树的任何一个节点变为根，但所有的边都不能改变。小x想问你，将根换为哪个节点能使小x爬到世界树上的每个节点耗费的体力值和最少。默认编号为1的点为初始根。

#### Input ####

第一行一个数n，表示有n个节点。  
第二行n个数ai，表示每个平台上的加速器的性能。  
第三至n+1行，每行三个数bi,ci,di分别表示这条无向边的起点，终点与耗费的能量值

#### Output ####

第一行一个数，表示要换成的节点，如果有多个点为根时耗费的体力值都最小，则输出编号最小的那个。如果保持为1是最优的，就输出1。  
第二行一个数，表示最小耗费的体力值。

#### Sample Input ####

4
    2 1 3 3
    1 2 3
    1 3 4
    2 4 6

#### Sample Output ####

1
    9

#### Data Constraint ####

对于20%的数据:n<=100  
对于40%的数据:n<=1000  
对于60%的数据:n<=8000  
对于80%的数据:n<=100000  
对于100%的数据:0<n<=700000;ai<=1000;1<=bi,ci<=n;di<=1000。  
数据保证一个点的加速器性能绝对小于等于它的所有的边所耗费的能量，保证所有节点都可以到达,保证没有数据与样例相同。

#### Hint ####

提示：  
样例解释：  
如果以第一个点为根，则需要耗费0(到1)+1(到2)+2(到3)+6(到4)=9的能量值。  
如果以第二个点为根，则需要耗费2(到1)+0(到2)+4(到3)+5(到4)=11的能量值。  
如果以第三个点为根，则需要耗费1(到1)+2(到2)+0(到3)+7(到4)=10的能量值。  
如果以第四个点为根，则需要耗费5(到1)+3(到2)+7(到3)+0(到4)=15的能量值。  
很明显以第一个点为根是最优的。

--------------------

考虑不换根怎么做， 那么每条边经过的次数就是它的子树大小。

如果换根， 那么考虑root的儿子x， 它的答案中只有root到x的边的贡献发生变化了。

发生的变化是减去root到x的贡献， 加上x到root的贡献。

于是求出root为1的答案， 然后再换根， 这样统计答案是O(1)的， 总共是O(N)的。

注意更新的顺序一定要按照dfs顺序， 还要开Long long.

--------------------

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <map>
    #define int long long
    using namespace std;
    inline int read() {
        int res=0;char c=getchar();bool f=0;
        while(!isdigit(c)) {
        if(c=='-')f=1;c=getchar();}
        while(isdigit(c))res=(res<<3)+(res<<1)+(c^48),c=getchar();
        return f?-res:res;
    }
    
    #define reg register
    #define N 700005
    
    int n;
    struct edge {
        int nxt, to, val;
    }ed[N*2];
    int head[N], cnt;
    int ine[N];
    
    inline void add(int x, int y, int z)
    {
        ed[++cnt] = (edge){head[x], y, z};
        head[x] = cnt;
    }
    
    int a[N], siz[N], fat[N];
    int ans, root = 1, res;
    int f[N];
    
    void dfs(int x, int fa)
    {
        siz[x] = 1;
        for (reg int i = head[x] ; i ; i = ed[i].nxt)
        {
            int to = ed[i].to;
            if (to == fa) continue;
            fat[to] = x;
            ine[to] = i;
            dfs(to, x);
            siz[x] += siz[to];
        }
    }
    
    int efs(int x, int fa, int in)
    {
        int sum = 0;
        for (reg int i = head[x] ; i ; i = ed[i].nxt)
        {
            int to = ed[i].to;
            if (to == fa) continue;
            sum += efs(to, x, i);
        }
        sum += siz[x] * (ed[in].val - a[fa]);
        return sum;
    }
    
    void ffs(int x, int fa, int in)
    {
        if (x != 1) f[x] = f[fa] - (siz[x] * (ed[in].val - a[fa])) + (n - siz[x]) * (ed[in].val - a[x]);
        for (reg int i = head[x] ; i ; i = ed[i].nxt)
        {
            int to = ed[i].to;
            if (to == fa) continue;
            ffs(to, x, i);
        }
    }
    
    signed main()
    {
        freopen("yggdrasil.in", "r", stdin);
        freopen("yggdrasil.out", "w", stdout);
        n = read();
        for (reg int i = 1 ; i <= n ; i ++) a[i] = read();
        for (reg int i = 1 ; i < n ; i ++)
        {
            int x = read(), y = read(), z = read();
            add(x, y, z);add(y, x, z);
        }
        dfs(1, 0);
        res = efs(1, 0, 0);
        ans = res;
        f[1] = ans;
        ffs(1, 0, 0);
        for (reg int i = 2 ; i <= n ; i ++) 
            if (f[i] < ans) {ans = f[i], root = i;}
        printf("%lld\n%lld\n", root, ans);
        return 0;
    }

转载于:https://www.cnblogs.com/BriMon/p/9451989.html