题目
点这里看题目。
BZOJ 上面是权限题目。
分析
第 K 小的问题无非两种方法——构造法或者二分法。
很显然如果构造的话在这里不太好处理，因此我们可以对于每一个点(u)，二分一下这个第 K 小路的长度。
检查的方法很简单，也就是计算一下从(u)出发的路径中，是否有 K 条以上的路径的长度小于等于二分长度。因此，我们只需要想办法快速求出从(u)出发的路径中有多少条的长度小于等于二分长度。
考虑一次点分治进行检查。以(u)为分治中心的时候，可以计算连通块内部的路径；剩下的路径不在连通块内部，但是一定以(u)的一个分治祖先作为路径的 LCA 。因此我们可以枚举分治祖先然后计算除(u)所在子树后剩下的路径。
由于本题的二分需要多次检查，我们就需要建立起点分树。对于点分树上的每一个点，我们惯例维护两个信息，一个是分治连通块中所有点到该点的距离，另一个是分治连通块中所有点到点分树父亲的距离。第一个用于直接计算，第二个用于减去多余的贡献。预处理的时候，将上述两个信息存下来（比如 vector ）后排序。检查的时候可以直接二分了。
时间：外部枚举和二分为(O(nlog_2V))，跳点分树(O(log_2n))，内部二分(O(log_2n))，其中(V=sum_{(u,v)in E} w(u,v))，即边权和。总体时间复杂度(O(nlog_2^2nlog_2V))。
代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5, MAXLOG = 20;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
struct edge
{
int to, nxt, w;
}Graph[MAXN << 1];
vector<int> dist[2][MAXN];
int f[MAXN][MAXLOG], dis[MAXN][MAXLOG], dep[MAXN];
int head[MAXN], siz[MAXN], mx[MAXN];
int N, K, all, cnt;
bool vis[MAXN];
void upt( int &x, const int v ) { x = MAX( x, v ); }
bool visible( const int u, const int fa ) { return u ^ fa && ! vis[u]; }
void addEdge( const int from, const int to, const int W )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from], Graph[cnt].w = W;
head[from] = cnt;
}
int getCen( const int u, const int fa )
{
int tmp, ret = 0;
mx[u] = 0, siz[u] = 1;
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( visible( v = Graph[i].to, fa ) )
{
tmp = getCen( v, u );
siz[u] += siz[v], upt( mx[u], siz[v] );
if( mx[tmp] < mx[ret] ) ret = tmp;
}
upt( mx[u], all - siz[u] );
if( mx[u] < mx[ret] ) ret = u;
return ret;
}
void DFS( const int u, const int fa, const int rt, const int d )
{
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( visible( v = Graph[i].to, fa ) )
f[v][++ dep[v]] = rt, dis[v][dep[v]] = d + Graph[i].w,
dist[0][rt].push_back( dis[v][dep[v]] ), dist[1][rt].push_back( dis[v][dep[v] - 1] ),
DFS( v, u, rt, d + Graph[i].w );
}
void divide( const int u )
{
vis[u] = true; DFS( u, 0, u, 0 ); int tmp = all;
dist[1][u].push_back( dis[u][dep[u]] ), dist[0][u].push_back( 0 );
sort( dist[1][u].begin(), dist[1][u].end() ), sort( dist[0][u].begin(), dist[0][u].end() );
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( ! vis[v = Graph[i].to] )
all = siz[v] > siz[u] ? tmp - siz[u] : siz[v],
divide( getCen( v, u ) );
}
int cal( const int u, const bool mod, const int len )
{
int l = 0, r = dist[mod][u].size() - 1, mid;
if( len < dist[mod][u][l] ) return 0;
if( dist[mod][u][r] <= len ) return r + 1;
while( r - l > 1 )
{
if( dist[mod][u][mid = l + r >> 1] <= len ) l = mid;
else r = mid - 1;
}
if( dist[mod][u][r] <= len ) return r + 1;
return l + 1;
}
int chk( const int u, const int len )
{
int ret = cal( u, 0, len ) - 1; //注意不能有距离为 0 的旅游路径！
for( int i = dep[u] ; i ; i -- )
{
ret += cal( f[u][i], 0, len - dis[u][i] );
ret -= cal( f[u][i + 1], 1, len - dis[u][i] );
}
return ret;
}
int main()
{
int l, r, tot = 0, mid;
read( N ), read( K );
for( int i = 1, a, b, c ; i < N ; i ++ )
read( a ), read( b ), read( c ), addEdge( a, b, c ), addEdge( b, a, c ), tot += c;
mx[0] = all = N, divide( getCen( 1, 0 ) );
for( int i = 1 ; i <= N ; i ++ ) f[i][dep[i] + 1] = i;
for( int x = 1 ; x <= N ; x ++ )
{
l = 0, r = tot;
while( r - l > 1 )
{
if( chk( x, mid = l + r >> 1 ) >= K ) r = mid;
else l = mid + 1;
}
if( chk( x, l ) >= K ) write( l ), putchar( '
' );
else write( r ), putchar( '
' );
}
return 0;
}