タイトル1536:ツリーの最小高さツリーの直径(パーソナルクラシックコード)
7019 ワード
タイトル1536:木の最小高さ
時間制限:5秒
メモリ制限:128メガ
タイトルの説明:
無方向ツリーを指定すると、ルートノードとして異なるノードを選択すると、異なる高さ(すなわち、ルートノードからリーフノードまでの距離の最大値)が得られ、このツリーの可能な最低高さが求められます.
入力:
入力には、複数のテストケースが含まれる場合があります.各テストケースについて、入力された第1の動作は整数n(1<=n<=1000000)である.次のn−1行に続き、各行は2つの整数uを含み、v(0<=u、v
出力:
各テストケースに対応して、このツリーの可能な最小高さを出力します.
サンプル入力:
サンプル出力:
時間制限:5秒
メモリ制限:128メガ
タイトルの説明:
無方向ツリーを指定すると、ルートノードとして異なるノードを選択すると、異なる高さ(すなわち、ルートノードからリーフノードまでの距離の最大値)が得られ、このツリーの可能な最低高さが求められます.
入力:
入力には、複数のテストケースが含まれる場合があります.各テストケースについて、入力された第1の動作は整数n(1<=n<=1000000)である.次のn−1行に続き、各行は2つの整数uを含み、v(0<=u、v
出力:
各テストケースに対応して、このツリーの可能な最小高さを出力します.
サンプル入力:
3
0 1
1 2
5
0 1
1 2
1 3
1 4サンプル出力:
1
1
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <fstream>
#include <vector>
#define Min(a,b) ((a)<(b)?(a):(b))
#pragma comment(linker, "/STACK:16777216")
using namespace std ;
typedef long long LL ;
const int size=1000008 ;
struct Edge{
int v ;
int next ;
};
Edge edge[size*2] ;
int vec[size] ,dist[size];
int id ,N;
bool visited[size] ;
inline void add_edge(int u ,int v){
edge[id].v=v ;
edge[id].next=vec[u] ;
vec[u]=id++ ;
}
void init(){
id=0 ;
fill(vec,vec+N,-1) ;
fill(dist,dist+N,0) ;
fill(visited,visited+N,0) ;
}
void dfs(int father,int high){
visited[father]=1 ;
dist[father]=high ;
for(int e=vec[father];e!=-1;e=edge[e].next){
int son=edge[e].v ;
if(visited[son])
continue ;
dfs(son,high+1) ;
}
}
int gao(){
init() ;
int u ,v ;
for(int i=1;i<N;i++){
scanf("%d%d",&u,&v) ;
add_edge(u,v) ;
add_edge(v,u) ;
}
dfs(0,0) ;
int start=max_element(dist,dist+N)-dist ;
//printf("%d
",start) ;
fill(dist,dist+N,0) ;
fill(visited,visited+N,0) ;
dfs(start,0) ;
int Height=*max_element(dist,dist+N) ;
if(Height&1)
return Height/2 +1 ;
else
return Height/2 ;
}
int main(){
while(scanf("%d",&N)!=EOF){
printf("%d
",gao()) ;
}
return 0 ;
}