题目链接
(Describe)
有一个(n)个节点的树，边有权值，定义两个节点之间的距离为两点之间的路径上的最小边权
给你(Q)个询问，问你与点(v)的距离大于等于(k)的点有多少个
(Solution)
这道题主要用并查集搞一下就好了啊.
离线的做.
- 首先将边按照权值排序,将询问的按照k排序
- 然后把权值大于等于(k)的放入并查集中,维护一个(siz)即节点的个数.
(End)
(Code)
#include<bits/stdc++.h>
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define rg register
using namespace std;
typedef long long ll;
int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
struct node{
int x,y,v;
}a[100010],b[100010];
int q[100010],pre[100010],siz[100010];
bool cmp(const node & a , const node & b){
return a.v>b.v;
}
int find(int x){
return pre[x]==x?x:pre[x]=find(pre[x]);
}
void join(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy)
pre[fx]=fy,siz[fy]+=siz[fx];
}
int main(){
int n=read(),m=read(),cnt=1;
for(int i=1;i<n;i++)
a[i].x=read(),a[i].y=read(),a[i].v=read(),pre[i]=i,siz[i]=1;
sort(a+1,a+n,cmp),pre[n]=n,siz[n]=1;
for(int i=1;i<=m;i++)
b[i].v=read(),b[i].x=read(),b[i].y=i;
sort(b+1,b+1+m,cmp);
for(int i=1;i<=m;i++){
while(a[cnt].v>=b[i].v)
join(a[cnt].x,a[cnt].y),cnt++;
q[b[i].y]=siz[find(b[i].x)]-1;
}
for(int i=1;i<=m;i++)
printf("%d
",q[i]);
}