516D Drazil and Morning Exercise
2024-10-07 06:00:20
分析
求出直径和最远距离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 ;
}
最新文章
- WebAPI使用多个xml文件生成帮助文档
- asp.net TextBoxWatermark添加水印提示
- [.net 面向对象编程基础] (23) 结束语
- set的用法
- Windows Azure 如何学习Azure
- .Net操作Excel
- POJ 2253 Frogger -- 最短路变形
- MySQL基础操作命令
- eclipse启动tomcat 访问http://localhost:8080 报404错误
- Linux远程连接与常用命令
- mysql版本升级
- android开发遇到的问题
- Vue.js的坑
- 如何将生产环境的字段类型从INT修改为BIGINT
- EF时,数据库字段和实体类不一致问题
- Vue js 的生命周期(看了就懂)
- Sharding-jdbc视频:当Sharding-jdbc遇到Spring Boot
- vue computed计算属性和watch监听属性解疑答惑
- python异常处理的两种写法
- LeetCode--No.016 3Sum Closest