分析

求出直径和最远距离d

之后我们以直径中点为根

发现父亲的d肯定不小于儿子的d

于是从下往上启发式合并维护与子树根的值相差L内的个数即可

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define int long long
priority_queue<int>q[];
int n,m,Q,L,d[],rt,ans;
vector<pair<int,int> >v[];
inline void dfs(int x,int fa){
for(int i=;i<v[x].size();i++)if(v[x][i].fi!=fa){
int y=v[x][i].fi,z=v[x][i].se;d[y]=d[x]+z;dfs(y,x);
}
}
inline void dfs2(int x,int fa,int sum){
d[x]=max(d[x],sum);
for(int i=;i<v[x].size();i++)if(v[x][i].fi!=fa){
int y=v[x][i].fi,z=v[x][i].se;dfs2(y,x,sum+z);
}
}
inline void mer(priority_queue<int> &x,priority_queue<int> &y){
if((int)y.size()>(int)x.size())swap(x,y);while(!y.empty())x.push(y.top()),y.pop();
}
inline void go(int x,int fa){
for(int i=;i<v[x].size();i++)if(v[x][i].fi!=fa){
int y=v[x][i].fi,z=v[x][i].se;go(y,x);mer(q[x],q[y]);
while(!q[x].empty())if(q[x].top()-d[x]>L)q[x].pop();else break;
}
ans=max(ans,(int)q[x].size());return;
}
signed main(){
int i,j,k;rt=;
scanf("%lld",&n);
for(i=;i<n;i++){
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
v[x].pb(mp(y,z));
v[y].pb(mp(x,z));
}
dfs(rt,);for(i=;i<=n;i++)if(d[i]>d[rt])rt=i;
memset(d,,sizeof(d));dfs(rt,);int ano=rt;
for(i=;i<=n;i++)if(d[i]>d[ano])ano=i;dfs2(ano,,);
for(i=;i<=n;i++)if(d[i]<d[rt])rt=i;
scanf("%lld",&Q);
while(Q--){
for(i=;i<=n;i++){while(!q[i].empty())q[i].pop();q[i].push(d[i]);}
scanf("%lld",&L);ans=;go(rt,);printf("%lld\n",ans);
}
return ;
}

最新文章

  1. WebAPI使用多个xml文件生成帮助文档
  2. asp.net TextBoxWatermark添加水印提示
  3. [.net 面向对象编程基础] (23) 结束语
  4. set的用法
  5. Windows Azure 如何学习Azure
  6. .Net操作Excel
  7. POJ 2253 Frogger -- 最短路变形
  8. MySQL基础操作命令
  9. eclipse启动tomcat 访问http://localhost:8080 报404错误
  10. Linux远程连接与常用命令
  11. mysql版本升级
  12. android开发遇到的问题
  13. Vue.js的坑
  14. 如何将生产环境的字段类型从INT修改为BIGINT
  15. EF时,数据库字段和实体类不一致问题
  16. Vue js 的生命周期(看了就懂)
  17. Sharding-jdbc视频:当Sharding-jdbc遇到Spring Boot
  18. vue computed计算属性和watch监听属性解疑答惑
  19. python异常处理的两种写法
  20. LeetCode--No.016 3Sum Closest

热门文章

  1. 面试必备:GET和POST的用法和区别
  2. mysql导入导出数据,备份,恢复数据
  3. last, lastb - 显示最近登录的用户列表
  4. laravel5.8 Auth::guide
  5. Git入门指南九:远程仓库的使用【转】
  6. zabbix 添加图行树
  7. InterlliJ idea文件夹里面无法新建java文件等
  8. flex布局总结回顾
  9. [BZOJ1299]巧克力棒(博弈论,线性基)
  10. openssl x.509证书