算法1
(暴力枚举) $O(M*Q)$
给一颗树,如果树上一点 u 与另一点 v 有联系,则他们间的距离必须大于 k 。
求对于一个 ki,找与给定的 vi 有联系的点个数。
我们可以建立一棵树,然后从v开始搜索,统计合法的点的数目,一共Q个查询,遍历所有的边M,整个时间复杂度为O(M*Q)
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=N*N;
int h[N],e[M],ne[M],w[M],idx; //存在树
int cnt;
void add(int a,int b,int c) //添加边
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs(int u,int fa,int k) //统计u出发的符合节点的数目
{
for(int i=h[u];i!=-1;i=ne[i]) //从u开始查找所有相邻的边
{
int j=e[i],we=w[i]; //走到的点和权重
if(j!=fa&&we>=k) //如果不是从父亲节点过来并且是权重大于等于k
{
cnt++; //节点数目增加
dfs(j,u,k); //统计j出发的节点数目
}
}
}
int main()
{
int n,q;
cin>>n>>q;
memset(h,-1,sizeof h); //初始化头节点
for(int i=1;i<n;i++) //构造树
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
while(q--)
{
int a,k;
cin>>k>>a;
cnt=0;
dfs(a,-1,k);
cout<<cnt<<endl;
}
return 0;
}
算法2
(并查集) $O(Q+M)$
我们需要将所有边的权重按照从大到小排序,然后将需要查询的点的k值按照从大到小排序,在查询每个点的时候,添加权重大于等于当前的k的边,构造新的并查集
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int p[N],cnt[N],ans[N];
struct edge //储存边
{
int u,v,w;
}e[N];
struct query //存储边
{
int k,v,id;
}q[N];
bool cmpe(edge a,edge b) //边的权重按照从大到小排序
{
return a.w>b.w;
}
bool cmpq(query a,query b)//查询的k值按照从大到小排序
{
return a.k>b.k;
}
int find(int x) //查找x的祖宗节点
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
void merge(int a,int b) //合并a和b两棵树
{
int fa=find(a),fb=find(b);
if(fa==fb) return ; //相同的根节点
cnt[fb]+=cnt[fa]; //更新节点数目
p[fa]=p[fb]; //合并树
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) //初始化每棵树,祖宗节点为自身,节点数目为1
{
p[i]=i;
cnt[i]=1;
}
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+n,cmpe); //将边按照权重从大到小排序
sort(q+1,q+1+m,cmpq); //将查询按照k从到到小排序
int j=1; //从最大的边开始
for(int i=1;i<=m;i++) //第i个查询
{
while(j<n&&e[j].w>=q[i].k)//将边的权重所有大于等于q[i].k的边加入树中
{
merge(e[j].u,e[j].v); //合并树
j++; //尝试下一个边
}
ans[q[i].id]=cnt[find(q[i].v)]-1; //集合中点的数目
}
for(int i=1;i<=m;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}