「Test」战略游戏

题意：一棵 $N$ 个点的树，每条边都有一个权值，设任意两点的相关值为两点路径中最短边的权值。现在有 $Q$ 个询问，每次询问 $k,v$，表示查询与节点 $v$ 相关值不小于 $k$ 的点的个数。

一道并查集加离线做法的题目。

我们先把所有边按权值从大到小排序，再将所有询问的 $k$ 从大到小排序，然后用两个指针 $i,j$ 分别维护询问和边，对每个询问，把比 $k$ 大的所有边都加入进来，把这些边的端点用并查集合并，同时用一个数组记录并查集中各个集合的元素数目，那么查询 $v$ 所在的集合的元素数目，减 $1$(除去自身)便是这个询问的答案。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=100010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,m;
int fa[maxn],size[maxn];
struct node
{
	int u;
	int v;
	int w;
}e[maxn];
struct question
{
	int k;
	int v;
	int id;
	int ans;
}q[maxn];
int cmp1(node a,node b)
{
	return a.w>b.w;
}
int cmp2(question a,question b)
{
	return a.k>b.k;
}
int cmp3(question a,question b)
{
	return a.id<b.id;
}
int getfa(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=getfa(fa[x]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+n,cmp1);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].k,&q[i].v);
		q[i].id=i;
	}
	for(int i=1;i<=n;i++)
	{
		size[i]=1;
		fa[i]=i;
	}
	sort(q+1,q+m+1,cmp2);
	int j=1;
	for(int i=1;i<=m;i++)
	{
		while(j<n&&q[i].k<=e[j].w)
		{
			int x=getfa(e[j].u);
			int y=getfa(e[j].v);
			if(x!=y)
			{
				fa[x]=y;
				size[y]+=size[x];
			}
			j++;
		}
		q[i].ans=size[getfa(q[i].v)]-1;
	}
	sort(q+1,q+m+1,cmp3);
	for(int i=1;i<=m;i++)
		printf("%d\n",q[i].ans);
	return 0;
}