洛谷P4185 [USACO18JAN]MooTube G 题解

题目链接：P4185 [USACO18JAN]MooTube G

题意：

给出一棵无根树， $m \le 10^5$ 次询问，给出 $k,v$ ，询问共有多少结点 $u$ 满足 $u$ 到 $v$ 的路径上最小边权不小于 $k$ 。

考虑把所有相互满足条件的结点用并查集合并

注意到当 $k$ 减小时，合并后的连通块数量单调递减

考虑将询问按 $k$ 降序排序，离线处理

每次去找没合并过的边显然太麻烦

继续利用单调性，将所有边按边权降序排序

这样我们扫一遍就能处理所有询问了

复杂度瓶颈在于排序。

时间复杂度 $O(m \log m)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

struct Edge {int u,v,w;}e[N];
struct Query{int k,v,id;}q[N];
int n,m,f[N],sz[N],ans[N];
void init(int n){for(int i=1; i<=n; i++) f[i]=i,sz[i]=1;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void merge(int u,int v)
{
    u=find(u);v=find(v);
    f[u]=v;
    sz[v]+=sz[u];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    init(n);
    for(int i=1; i<n; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    for(int i=1; i<=m; i++)
        cin >> q[i].k >> q[i].v,q[i].id=i;
    sort(e+1,e+1+n,[](Edge a,Edge b){return a.w>b.w;});
    sort(q+1,q+1+m,[](Query a,Query b){return a.k>b.k;});
    for(int i=1,j=1; i<=m; i++)
    {
        for(; j<=n&&q[i].k<=e[j].w; j++)
            merge(e[j].u,e[j].v);
        ans[q[i].id]=sz[find(q[i].v)]-1;
    }
    for(int i=1; i<=m; i++)
        cout << ans[i] << '\n';
    return 0;
}