好恶心啊
没加快读的时候是最后一个点1.01
加了就是1.00
为啥还T了,求大佬看看代码的问题
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std ;
const int INF = 0x3f3f3f3f ;
int n , k , vis[100005] , h[100005] , son[100005] , l , r , cnt = 0 ;
int nxt[200005] , to[200005] , head[100005] ;
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read ( )
{
register char ch = gc ( ) ;
register int x = 0 ;
while ( ch < '0' || ch > '9' )
ch = gc ( ) ;
while ( ch >= '0' && ch <= '9' )
x = x * 10 + ch - 48 , ch = gc ( ) ;
return x ;
}
inline void insert ( register int u , register int v )
{
++ cnt ;
nxt [ cnt ] = head [ u ] ;
to [ cnt ] = v ;
head [ u ] = cnt ;
}
inline void dfs1 ( register int x , register int la )
{
h [ x ] = 1 ;
int ax1 = 0 , ax2 = 0 ;
for ( register int i = head [ x ] ; i ; i = nxt [ i ] )
{
int y = to [ i ] ;
if ( y == la )
continue ;
dfs1 ( y , x ) ;
if ( h [ y ] > h [ ax1 ] )
{
son [ x ] = y ;
ax2 = ax1 ;
ax1 = y ;
}
else if ( h [ y ] > h [ ax2 ] )
ax2 = y ;
}
h [ x ] = h [ ax1 ] + 1 ;
if ( h [ ax1 ] + h [ ax2 ] + 1 > l )
{
l = h [ ax1 ] + h [ ax2 ] + 1 ;
r = x ;
for ( register int i = 1 ; i <= ( h [ ax1 ] - h [ ax2 ] ) / 2 ; ++ i )
r = son [ r ] ;
}
}
inline void dfs2 ( register int x , register int la )
{
h [ x ] = 1 ;
int ax1 = 0 , ax2 = 0 ;
for ( register int i = head [ x ] ; i ; i = nxt [ i ] )
{
int y = to [ i ] ;
if ( y == la )
continue ;
dfs2 ( y , x ) ;
if ( h [ y ] > h [ ax1 ] )
{
son [ x ] = y ;
ax2 = ax1 ;
ax1 = y ;
}
else if ( h [ y ] > h [ ax2 ] )
ax2 = y ;
}
h [ x ] = h [ ax1 ] + 1 ;
}
struct Node
{
int x , leng ;
Node ( int x = 0 , int leng = INF ) : x ( x ) , leng ( leng ) { }
friend bool operator < ( Node u , Node v )
{
return u .leng < v .leng ;
}
} ;
priority_queue < Node > q ;
int main ( )
{
n = read ( ) , k = read ( ) ;
for ( register int i = 1 ; i < n ; ++ i )
{
int u = read ( ) , v = read ( ) ;
insert ( u , v ) ;
insert ( v , u ) ;
}
dfs1 ( 1 , 0 ) ;
dfs2 ( r , 0 ) ;
q .push ( Node ( r , h [ r ] ) ) ;
son [ r ] = -1 ;
for ( register int i = 1 ; i <= k ; ++ i )
{
Node tmp = q .top ( ) ; q .pop ( ) ;
int x = tmp .x ;
for ( register int j = head [ x ] ; j ; j = nxt [ j ] )
{
int y = to [ j ] ;
if ( son [ y ] == -1 )
continue ;
q .push ( Node ( y , h [ y ] ) ) ;
son [ y ] = -1 ;
}
}
Node tmp = q .top ( ) ;
printf ( "%d\n" , tmp .leng ) ;
return 0 ;
}