# [USACO18JAN] MooTube G

题意：

给出一棵 $n$ 个点的树及每条边的边权，定义任意两个点的熟悉度为连接这两个点的路径上边权的最小值。再给出 $Q$ 个询问，每次询问给出数对 $（k_i,v_i）$ ，要求计算出有多少个节点与节点 $v_i$ 的熟悉度大于等于 $k_i$ 。

解法：
离线做，把询问从大到小排序，把给的边权值也从大到小排序，以询问的权值为下限，不断加入边，那么这样加入进去的边都是有意义的，无论怎么样边权最小值只可能为询问的当前询问的边权值，这样就解决了。

写一个并查集，并且记录每个并查集的大小，答案就是询问的点所在并查集的大小减一（需要减去自己）。

像这种对询问进行离线，并且框定下下限的都是典题。
还有一道题目类似的，可以练习一下（没数据）。

Code

	//https://www.luogu.com.cn/problem/P4185
	// 写个并查集就可以了
	#include <iostream>
	#include <algorithm>
	#include <cstring>
	#include <cstdio>
	#include <cmath>
	#include <map>
	#include <queue>
	#include <stack>
	#include <set>
	#include <iomanip>
	#define int long long
	using namespace std;
	const int MAXN=1e6+10;
	struct edgebox{
	int nex,to,val;
	}box[MAXN];
	struct questbox{
	int to,val,fla;
	}quebox[MAXN];
	int fa[MAXN],sum[MAXN],ans[MAXN];
	bool cmp(edgebox a,edgebox b){
	return a.val>b.val;
	}
	bool cmp2(questbox a,questbox b){
	return a.val>b.val;
	}
	int find(int now){
	if(fa[now]==now){
	return now;
	}
	return fa[now]=find(fa[now]);
	}
	void add(int now){
	int a=box[now].nex;
	int b=box[now].to;
	int fx=find(a);
	int fy=find(b);
	if(fx!=fy){
	if(sum[fx]>sum[fy]){
	swap(fx,fy);
	}
	fa[fx]=fy;
	sum[fy]+=sum[fx];
	sum[fx]=0;
	}
	return;
	}
	signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
	fa[i]=i;
	sum[i]=1;
	}
	for(int i=1;i<n;i++){// 边
	cin>>box[i].nex>>box[i].to>>box[i].val;
	}
	sort(box+1,box+n,cmp);
	for(int i=1;i<=m;i++){// 询问
	cin>>quebox[i].val>>quebox[i].to;
	quebox[i].fla=i;
	}
	sort(quebox+1,quebox+1+m,cmp2);
	int nowceil=0;
	int nownum=0;
	for(int i=1;i<=m;i++){
	for(int j=nownum+1;j<=n;j++){
	if(box[j].val<quebox[i].val){
	nownum=j-1;
	break;
	}
	add(j);
	}
	ans[quebox[i].fla]=sum[find(quebox[i].to)];
	}
	for(int i=1;i<=m;i++){
	cout<<ans[i]-1<<endl;
	}
	}