【ICPC2021 上海站】H题 Life is a Game 题解

题目大意

给定一个 $n$ 个节点和 $m$ 条边 $(u, v, w)$ 的图，有 $1 \le n, m, q \le 10^5$。

每次询问为以下含义：

你最开始在 $x$ 节点，有 $k$ 点能力值，每次第一次到一个节点 $i$，就能获得 $a[i]$ 点能力值（最开始当然也会获得 $x$ 节点的能力值）。

而通过每一条边需要有最少 $w_i$ 的能力值，通过边不会减少能力值，可以多次经过同一个点和边，求你最后的能力值最多为多少。

原题地址

思路

主要思想还是 Kruskal 重构树，不了解的可以去了解一下，或者看看我写的简要版本，我写的比较简略，完全没有学过的可以去看看别的博客，比如这个。

为什么会想到 Kruskal 重构树呢？

• 我们最好情况一定是遍历完所有的点，那么最优路线一定是最小生成树
• 我们能否继续到达某个点很大一部分是根据最小生成树路径上权值最大的边

那么看起来就可以用 Kruskal 重构树解决，所以我们不妨来试一试 （其实蒟蒻根本想不到别的方法了 QAQ）

观察一波 Kruskal 重构树的性质：

• 边权越大的形成的点都越靠上
• 当你到达了一个非叶子节点，就意味着你一定可以到达这个点子树上的所有叶子节点

那么我们发现，使用 Kruskal 重构树确实是可以解决的，我们使用倍增的方法，依次往上找。

$sum[x]$ 记录的是在子树 $x$ 上能获得的能力值。

$maxNum[x][i]$ 记录的是从 $x$ 到它的 $i$ 级祖先中，最大的边权比能够获得的能力值大多少。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 2e5 + 7;

struct Edge {
    int from, to, dis;
}e[maxN], initEdge[maxN];

int n, m, q, head[maxN], cnt, tot, fa[maxN], f[maxN][23];
long long sum[maxN], maxNum[maxN][23], val[maxN];

inline void add(int u, int v, int w = 0)
{
    e[++cnt].from = head[u];
    e[cnt].to = v;
    e[cnt].dis = w;
    head[u] = cnt;
}

bool cmp(Edge x, Edge y)
{
    return x.dis < y.dis;
}

int Find(int x)
{
    return fa[x] == x? x : fa[x] = Find(fa[x]);
}

inline void KruskalTree() //Kruskal重构树
{
    sort(initEdge + 1, initEdge + 1 + m, cmp);
    for(int i = 1; i <= n; ++i)
        fa[i] = i;
    tot = n;    
    for(int i = 1; i <= m; ++i) {
        if(tot == (n << 1) - 1)
            break;
        int fx = Find(initEdge[i].from), fy = Find(initEdge[i].to);
        if(fx == fy)
            continue;
        val[++tot] = initEdge[i].dis;
        fa[tot] = fa[fx] = fa[fy] = tot;
        add(tot, fx); add(tot, fy);
    }    
}

void dfs1(int x) //记录祖先,计算sum数组
{
    if(x <= n) {
        sum[x] = val[x];
        return ;
    }
    for(int i = head[x]; i; i = e[i].from) {
        int y = e[i].to;
        f[y][0] = x; 
        dfs1(y);
        sum[x] += sum[y];
    }
}

void dfs2(int x) //更新maxNum
{
    maxNum[x][0] = val[f[x][0]] - sum[x];
    for(int i = 1; i <= 19; ++i) {
        f[x][i] = f[f[x][i - 1]][i - 1];
        maxNum[x][i] = max(maxNum[x][i - 1], maxNum[f[x][i - 1]][i - 1]);
    }
    for(int i = head[x]; i; i = e[i].from) {
        int y = e[i].to;
        dfs2(y);
    }
}

inline int query(int x, int k) //倍增求结果
{
    for(int i = 19; i >= 0; --i)
        if(f[x][i] && maxNum[x][i] <= k)
            x = f[x][i];
    return sum[x];        
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; ++i) 
        scanf("%lld", &val[i]);
    for(int i = 1; i <= m; ++i)
        scanf("%d%d%d", &initEdge[i].from, &initEdge[i].to, &initEdge[i].dis);    
    KruskalTree();
    dfs1(tot); dfs2(tot); //注意,tot节点是新树的根节点
    for(int i = 1; i <= q; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", y + query(x, y));
    }
    return 0;
}