洛谷P4185-MooTube_G-题解

MooTube G

题目背景

本题与 银组同名题目 在题意上一致，唯一的差别是数据范围。

题目描述

在业余时间，Farmer John 创建了一个新的视频共享服务，他将其命名为 MooTube。在 MooTube 上，Farmer John 的奶牛可以录制，分享和发现许多有趣的视频。他的奶牛已经发布了 $N$ 个视频（$1 \leq N \leq 10^5$），为了方便将其编号为 $1 \ldots N$ 。然而，FJ 无法弄清楚如何帮助他的奶牛找到他们可能喜欢的新视频。

FJ 希望为每个 MooTube 视频创建一个“推荐视频”列表。这样，奶牛将被推荐与他们已经观看过的视频最相关的视频。

FJ 设计了一个“相关性”度量标准，顾名思义，它确定了两个视频相互之间的相关性。他选择 $N-1$ 对视频并手动计算其之间的相关性。然后，FJ 将他的视频建成一棵树，其中每个视频是节点，并且他手动将 $N-1$ 对视频连接。为了方便，FJ 选择了 $N-1$ 对，这样任意视频都可以通过一条连通路径到达任意其他视频。 FJ 决定将任意一对视频的相关性定义为沿此路径的任何连接的最小相关性。

Farmer John 想要选择一个 $K$ 值，以便在任何给定的 MooTube 视频旁边，推荐所有其他与该视频至少有 $K$ 相关的视频。然而，FJ 担心会向他的奶牛推荐太多的视频，这可能会分散他们对产奶的注意力！因此，他想设定适当的 $K$ 值。 Farmer John希望得到您的帮助，回答有关 $K$ 值的推荐视频的一些问题。

输入格式

第一行输入包含 $N$ 和 $Q$（$1 \leq Q \leq 10^5$）。

接下来的 $N-1$ 行描述了 FJ 手动比较的一对视频。 每行包括三个整数 $p_i$，$q_i$ 和 $r_i$（$1 \leq p_i, q_i \leq N$，$1 \leq r_i \leq 10^9$），表示视频 $p_i$ 和 $q_i$ 已连接并且相关性为 $r_i$。

接下来的 $Q$ 行描述了 Farmer John 的 $Q$ 个问题。每行包含两个整数，$k_i$ 和 $v_i$（$1 \leq k_i \leq 10^9$，$1 \leq v_i \leq N$），表示 FJ 的第 $i$ 个问题询问中当 $K = k_i$ 时，第 $v_i$ 个视频推荐列表中将推荐的视频数。

输出格式

输出 $Q$ 行。在第 $i$ 行，输出 FJ 的第 $i$ 个问题的答案。

样例 #1

样例输入 #1

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

样例输出 #1

3
0
2

P4185 [USACO18JAN] MooTube G - 洛谷

思路

要求推荐一个视频的推荐视频数，其实就是求一个图节点的相邻节点的权值大于 $k$ 的个数。为此，我们不如这么想，与一个节点相连的节点（满足权值大于$k$的）都是以这个节点为根节点的树，问这棵树的节点树有多少。为此，我们的问题变成了一个类似最小生成树的问题。对于给定的图，我们可以先按照权值从大到小排序，对于给定的 $k_i,v_i$ 我们按照 $k_i$ 的大小进行排序，然后每次将大于 $k_i$ 的权值的两点合并，成为一棵树，这样，这颗树的节点数就是我们要找的答案。这样子写还有一个好处就是，搜索的过程中可以避免重复搜索。如果直接进行暴力搜索，由于题目数据量比较大，容易TLE

C++代码

#include <iostream>
#include <vector>
#include <numeric>
//C++20以下的同学记得 #include<algorithm>
template<typename T>
class UnionFindSet {
    std::vector<T> trees, size;
public:
    explicit UnionFindSet(T len) : trees(len << 1), size((len << 1), 1) {
        std::iota(trees.begin(), trees.begin() + len, len);
        std::iota(trees.begin() + len, trees.end(), len);
    }

    T find(const T &x) {
        return trees[x] == x ? x : trees[x] = find(trees[x]);
    }

    void unite(const T &x, const T &y) {
        T &&fx = find(x), &&fy = find(y);
        if (fx == fy) return;
        if (size[fx] < size[fy]) std::swap(fx, fy);
        trees[fy] = fx;
        size[fx] += size[fy];
    }

    void erase(const T &x) {
        --size[find(x)];
        trees[x] = x;
    }

    void move(const T &x, const T &y) {
        T &&fx = find(x), &&fy = find(y);
        if (fx == fy) return;
        trees[x] = fy;
        --size[fx], ++size[fy];
    }

    const T &getSize(const T &x) {
        return size[find(x)];
    }
};

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie();
    i64 N, Q;
    std::cin >> N >> Q;
    std::vector<std::pair<std::pair<i64, i64>, i64> > graph(N - 1), queries(Q);
    std::vector<i64> ans(Q);
    UnionFindSet<i64> ufs(N + 1);
    for (auto &i: graph)
        std::cin >> i.first.first >> i.first.second >> i.second;
    //用于储存输入的顺序
    i64 times = 0;
    for (auto &i: queries) {
        std::cin >> i.first.first >> i.first.second;
        i.second = times++;
    }
    std::sort(graph.begin(), graph.end(), []
            (const std::pair<std::pair<i64, i64>, i64> &x,
             const std::pair<std::pair<i64, i64>, i64> &y)
             { return x.second < y.second; });
    std::sort(queries.begin(), queries.end(), []
            (const std::pair<std::pair<i64, i64>, i64> &x,
             const std::pair<std::pair<i64, i64>, i64> &y)
             { return x.first.first > y.first.first; });
    //避免重复搜索带来的性能损耗
    i64 pos = graph.size() - 1;
    for (auto &i: queries) {
        for (;pos >= 0; --pos) {
            if (i.first.first > graph[pos].second)
                break;
            ufs.unite(graph[pos].first.first, graph[pos].first.second);
        }
        //答案要按照输入的顺序储存
        ans[i.second] = ufs.getSize(i.first.second) - 1;
    }
    for (auto &i: ans)
        std::cout << i << std::endl;
    return 0;
}