Description
给定一棵(N)个结点的树,结点用正整数(1 dots N)编号,每条边有一个正整数权值。用(d(a, b))表示从结点(a)到结点(b)路径上经过边的权值和,其中要求(a < b)。将这(frac{N(N-1)}{2})个距离值从大到小排序,输出前(M)个距离值。
Input
第一行包含两个正整数(N,M)。
下面(N − 1)行,每行三个正整数(a, b, c (a, b le N, c le 10,000)),表示结点(a)和结点(b)间有一条权值为(c)的边相连。
Output
共(M)行,每行一个正整数,第(i)行表示排在第(i)个的距离值。
Sample Input
5 10
1 2 1
1 3 2
2 4 3
2 5 4
Sample Output
7
7
6
5
4
4
3
3
2
1
Hint
(N le 50000,M le min(frac{N(N-1)}{2},30,000))
点分治＋Ｋ路归并。由于树上的每条路径必定经过一个重心，在进行点分治时我们可以枚举到所有的路径。将重心到每个点的距离按dfs序插入数组(可以把每次分治的结果都插入数组中，数组开(O(NlogN)))中。由于保证枚举的两个点不在一棵子数中，每个点对应的链在dfs数组中一定是段连续的区间，故可以采用超级钢琴的做法。代码如下：
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<set>
#include<vector>
using namespace std;
#define maxn (100010)
int N,M,next[maxn],toit[maxn],len[maxn],side[maxn],L,R,f[20][maxn*10],bit[maxn*10];
int cnt = 1,num,size[maxn],large[maxn],dis[maxn*10],best; bool vis[maxn];
struct node
{
int pos,l,r,mx,key;
friend inline bool operator <(const node &a,const node &b) { return a.key > b.key; }
};
vector <node> vec; multiset <node> S;
inline void add(int a,int b,int c) { next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b; len[cnt] = c; }
inline void ins(int a,int b,int c) { add(a,b,c); add(b,a,c); }
inline void getroot(int now,int fa,int rest)
{
size[now] = 1; large[now] = 0;
for (int i = side[now];i;i = next[i])
{
if (toit[i] == fa||vis[toit[i]]) continue;
getroot(toit[i],now,rest);
size[now] += size[toit[i]];
large[now] = max(large[now],size[toit[i]]);
}
large[now] = max(large[now],rest-size[now]);
if (large[now] < large[best]) best = now;
}
inline int find_root(int now,int rest) { best = 0; getroot(now,0,rest); return best; }
inline void dfs(int now,int fa,int d)
{
dis[++cnt] = d; vec.push_back((node){cnt,L,R,0,0});
for (int i = side[now];i;i = next[i])
if (toit[i] != fa&&!vis[toit[i]])
dfs(toit[i],now,d+len[i]);
}
inline void cut(int now)
{
vis[now] = true; L = R = ++cnt;
for (int i = side[now];i;i = next[i])
{
if (vis[toit[i]]) continue;
dfs(toit[i],now,len[i]); R = cnt;
}
for (int i = side[now];i;i = next[i])
if (!vis[toit[i]]) cut(find_root(toit[i],size[toit[i]]));
}
inline int query(int l,int r)
{
int len = r-l+1,lg = bit[len];
if (dis[f[lg][l]] > dis[f[lg][r-(1<<lg)+1]]) return f[lg][l];
else return f[lg][r-(1<<lg)+1];
}
int main()
{
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
scanf("%d %d",&N,&M);
for (int i = 1,a,b,c;i < N;++i) scanf("%d %d %d",&a,&b,&c),ins(a,b,c);
large[0] = 1<<30; cnt = 0; cut(find_root(1,N));
for (int i = 1;(1 << i) <= (cnt<<1);++i)
for (int j = (1<<(i-1));j <= (1<<i)-1&&j <= cnt;++j) bit[j] = i-1;
for (int i = 1;i <= cnt;++i) f[0][i] = i;
for (int i = 1;i <= bit[cnt];++i)
for (int j = 1;j+(1<<i)-1 <= cnt;++j)
{
if (dis[f[i-1][j]] > dis[f[i-1][j+(1<<(i-1))]]) f[i][j] = f[i-1][j];
else f[i][j] = f[i-1][j+(1<<(i-1))];
}
int nn = vec.size();
for (int i = 0;i < nn;++i)
{
node tmp = vec[i];
tmp.mx = query(tmp.l,tmp.r); tmp.key = dis[tmp.pos]+dis[tmp.mx];
S.insert(tmp);
}
for (int i = 1;i <= M;++i)
{
node now = *S.begin(); S.erase(S.begin());
printf("%d
",now.key);
if (now.mx > now.l)
{
node tmp; tmp = now;
tmp.mx = query(tmp.l,tmp.mx-1);
tmp.key = dis[tmp.mx]+dis[tmp.pos];
tmp.r = now.mx-1; S.insert(tmp);
}
if (now.mx < now.r)
{
node tmp; tmp = now;
tmp.mx = query(tmp.mx+1,tmp.r);
tmp.key = dis[tmp.mx]+dis[tmp.pos];
tmp.l = now.mx+1; S.insert(tmp);
}
}
fclose(stdin); fclose(stdout);
return 0;
}