hdu 4607 Park Visit
2024-08-26 07:41:57
http://acm.hdu.edu.cn/showproblem.php?pid=4607
先求树的直径 方法:两遍bfs ,任选一点 a 求到a点最远的一点b ,然后 求到b点最远点 c
这样 b和c之间的路径为 树的直径
然后讨论
假设直径上的点个数为 k 要访问的点个数为 v
1)如果v<=k 则可以直接在直径上参观 路径为 v-1
2)如果v>k 首先还是要走直径 但是 m=v-k 这m个点要到其他枝叶上访问 一共要花费 2*m
代码:
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
#include<queue>
#include<stdexcept>
#include<bitset>
#include<cassert>
#include<deque>
#include<numeric> using namespace std; typedef long long ll;
typedef unsigned int uint;
const double eps=1e-12;
const int INF=0x3f3f3f3f;
const ll MOD=1000000007;
const int N=200005;
int head[N],I;
struct node
{
int j,next;
}edge[N];
int dist[N];
void add(int i,int j)
{
edge[I].j=j;
edge[I].next=head[i];
head[i]=I++;
}
int bfs(int x1,int n)
{
queue<int>qt;
memset(dist,-1,sizeof(dist));
dist[x1]=0;
qt.push(x1);
while(!qt.empty())
{
int x=qt.front();
qt.pop();
for(int t=head[x];t!=-1;t=edge[t].next)
{
int j=edge[t].j;
if(dist[j]==-1)
{
dist[j]=dist[x]+1;
qt.push(j);
}
}
}
int k=x1;
for(int i=1;i<=n;++i)
if(dist[i]>dist[k])
k=i;
return k;
}
int main()
{
//freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d %d",&n,&m);
memset(head,-1,sizeof(head));I=0;
for(int i=1;i<n;++i)
{
int l,r;
scanf("%d %d",&l,&r);
add(l,r);
add(r,l);
}
int k=bfs(1,n);
k=bfs(k,n);
k=dist[k]+1;
while(m--)
{
int a;
scanf("%d",&a);
if(a<=k)
printf("%d\n",a-1);
else
printf("%d\n",k-1+2*(a-k));
}
}
return 0;
}
最新文章
- Linux的find命令
- C++ 必知必会:条款15 成员的指针并非指针
- shader 汇编
- Git权威指南 读笔(4)
- 使用bootstrap table小记(表格组件)
- LeetCode 84. Largest Rectangle in Histogram 直方图里的最大长方形
- JSON详细总结
- 生成ssl秘钥的方法(纯粹本人记录用的,勿踩)
- 翻译:Identifier Qualifiers标识限定符
- JavaScript Cookie使用实例
- mysql数据库的安装步骤
- 解决Windows服务无法访问网络映射盘的问题
- npm 安装cnpm淘宝镜像时报错解决
- TensorFlow+Keras 03 TensorFlow 与 Keras 介绍
- Linux服务器性能分析与调优
- linux_软件安装
- HDU 5792 World is Exploding(树状数组+离散化)
- Understanding Complex Event Processing (CEP)/ Streaming SQL Operators with WSO2 CEP (Siddhi)
- Weblogic 错误 <;BEA-000403>; <;BEA-000438>;解决办法
- springcloud使用Hystrix实现微服务的容错处理