并查集练习

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define pb push_back
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;

const int N = 1e5+10;
int n, q, s[N], cnt[N], ans[N];
struct _ {int u,v,w;} e[N];
struct __ {int k,v,id;} qry[N];
int Find(int x) {return s[x]?s[x]=Find(s[x]):x;}
void add(int x, int y) {
	x = Find(x), y = Find(y);
	if (x!=y) s[x]=y,cnt[y]+=cnt[x];
}
int main() {
	scanf("%d%d", &n, &q);
	REP(i,1,n-1) scanf("%d%d%d", &e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+n,[](_ a,_ b){return a.w>b.w;});
	REP(i,1,q) scanf("%d%d", &qry[i].k, &qry[i].v),qry[i].id=i;
	sort(qry+1,qry+1+q,[](__ a,__ b){return a.k>b.k;});
	REP(i,1,n) cnt[i] = 1;
	int now = 1;
	REP(i,1,q) {
		while (now<=n-1&&e[now].w>=qry[i].k) { 
			add(e[now].u,e[now].v),++now;
		}
		ans[qry[i].id] = cnt[Find(qry[i].v)];
	}
	REP(i,1,q) printf("%d\n", ans[i]-1);
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define pb push_back
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;

const int N = 1e5+10;
int n, q, tot, s[N<<1], val[N<<1];
vector<int> g[N<<1];
int sz[N<<1], fa[N<<1][20];
struct _ {int u,v,w;} e[N];
int Find(int x) {return s[x]?s[x]=Find(s[x]):x;}
void dfs(int x, int f) {
	sz[x] = 1;
	fa[x][0] = f;
	REP(i,1,19) fa[x][i]=fa[fa[x][i-1]][i-1];
	for (int y:g[x]) dfs(y,x),sz[x]+=sz[y];
}
int main() {
	scanf("%d%d", &n, &q);
	REP(i,1,n-1) scanf("%d%d%d", &e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+n,[](_ a,_ b){return a.w>b.w;});
	int tot = n;
	REP(i,1,n-1) {
		int u=Find(e[i].u),v=Find(e[i].v);
		s[u] = s[v] = ++tot, val[tot]=e[i].w;
		g[tot].pb(u), g[tot].pb(v);
	}
	dfs(tot,0);
	REP(i,1,q) {
		int k, v;
		scanf("%d%d", &k, &v);
		PER(i,0,19) if (val[fa[v][i]]>=k) v=fa[v][i];
		printf("%d\n", sz[v]>>1);
	}
}