BFS求树的直径。
/*
bfs+求树的直径
关键:if k<=maxs+1 直接输出k-1;
else: k肯定的是包括最长路。先从最长路的起点出发,再走分支,最后到达最长路的终点。
因此是2*(k-(maxs+1))+maxs;
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<math.h>
using namespace std;
typedef long long ll;
//typedef __int64 int64;
const int maxn = 100005;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;
struct Node{
int v,next;
}edge[ maxn<<1 ];
int cnt,head[ maxn ];
int vis[ maxn ],dis[ maxn ];
int maxs,maxNode;
void init(){
cnt = 0;
memset( head,-1,sizeof( head ) );
}
void addedge( int a,int b ){
edge[ cnt ].v = b;
edge[ cnt ].next = head[ a ];
head[ a ] = cnt++;
edge[ cnt ].v = a;
edge[ cnt ].next = head[ b ];
head[ b ] = cnt++;
}
void bfs( int s,int n ){
memset( vis,0,sizeof( vis ) );
vis[ s ] = 1;
queue<int>q;
q.push( s );
//for( int i=0;i<=n;i++ )
//dis[ i ] = inf;
dis[ s ] = 0;
maxs = 0;
while( !q.empty() ){
int cur = q.front();
q.pop();
if( dis[ cur ]>maxs ){
maxs = dis[ cur ];
maxNode = cur;
}
//maxs = max( maxs,dis[ cur ] );
for( int i=head[ cur ];i!=-1;i=edge[ i ].next ){
int v = edge[ i ].v;
if( vis[ v ]==1 ) continue;
vis[ v ] = 1;
dis[ v ] = dis[ cur ]+1;
q.push( v );
}
}
return ;
}
int main(){
int T;
scanf("%d",&T);
while( T-- ){
int n,m;
scanf("%d%d",&n,&m);
int a,b;
init();
int N = n-1;
while( N-- ){
scanf("%d%d",&a,&b);
addedge( a,b );
}
bfs( 1,n );
bfs( maxNode,n );
//maxs=the R of the tree
while( m-- ){
scanf("%d",&b);
if( b<=maxs+1 ) printf("%d\n",b-1);
else printf("%d\n",2*(b-maxs-1)+maxs);
}
}
return 0;
}
分享到:
相关推荐
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
杭电OnlineJudge 200-2099的解题报告
acm入门训练和日常训练 对于初学者以及acm爱好者有叫大帮助
hdu 1695 GCD(欧拉函数+容斥原理).docx
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
HDU的一题........HDU DP动态规
hdu 1574 passed sorce
acm hdu as easy as a+b
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241