【BZOJ3784】树上的路径
Description
给定一个N个结点的树，结点用正整数1..N编号。每条边有一个正整数权值。用d(a,b）表示从结点a到结点b路边上经过边的权值。其中要求a<b.将这n*(n-1)/2个距离从大到小排序，输出前M个距离值。
Input
第一行两个正整数N,M
下面N-1行，每行三个正整数a,b,c(a,b<=N，C<=10000)。表示结点a到结点b有一条权值为c的边。
Output
共M行，如题所述.
Sample Input
5 10
1 2 1
1 3 2
2 4 3
2 5 4
1 2 1
1 3 2
2 4 3
2 5 4
Sample Output
7
7
6
5
4
4
3
3
2
1
7
6
5
4
4
3
3
2
1
HINT
N<=50000,M<=Min(300000,n*(n-1) /2 )
题解：“总有那么一种序列，可以满足你某道题的所需的一切性质~”
没错，听说过DFS序吗，听说过BFS序吗，如果你都听说过，那么你听说过点分治序吗？
没错，点分治序，顾名思义，就是点分治时扫过的序列（包括每次找到的重心和从重心出发依次DFS过的所有子树），它的长度是nlogn的。那么这样一个序列有什么性质呢？
如果我们已经确定了一个分治中心和它的子树中的一条链，我们想找到这个分治中心的另一条链（亦或是这个分治中心本身）和它来组成一条路径，那么这些路径的端点在什么位置呢？没错，他们在点分治序上正好是一段连续的序列！并且根据点分治的原理，通过这样我们可以找到树上所有的路径。
那么问题就变成了：给你一个序列，你每次可以从中选取一个二元组(a,b)，其中对于每一个b，可以与它搭配的a都在一段给定的区间里。每个二元组的值是a的权值+b的权值，求前k大的二元组。这不就是BZOJ2006超级钢琴吗？直接ST表就好了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <utility>
#include <queue>
#define mp(A,B,C,D) make_pair(make_pair(A,B),make_pair(C,D))
using namespace std;
const int maxn=50010;
typedef pair<int,int> pii;
int n,m,cnt,maxx,tot,root,nm;
int sm[800010][20],to[maxn<<1],next[maxn<<1],val[maxn<<1],head[maxn],siz[maxn];
int lp[800010],rp[800010],v[800010],vis[maxn],Log[800010];
priority_queue<pair<pii,pii> > pq;
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int ms(int a,int b)
{
return v[a]>v[b]?a:b;
}
void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
void getr(int x,int fa)
{
siz[x]=1;
int i,mx=0;
for(i=head[x];i!=-1;i=next[i])
{
if(vis[to[i]]||to[i]==fa) continue;
getr(to[i],x),siz[x]+=siz[to[i]],mx=max(mx,siz[to[i]]);
}
if(maxx>max(mx,tot-siz[x])) root=x,maxx=max(mx,tot-siz[x]);
}
void getd(int x,int fa,int dep)
{
v[++nm]=dep,lp[nm]=lp[nm-1],rp[nm]=rp[nm]?rp[nm]:rp[nm-1];
for(int i=head[x];i!=-1;i=next[i])
{
if(vis[to[i]]||to[i]==fa) continue;
getd(to[i],x,dep+val[i]);
}
}
void dfs(int x)
{
vis[x]=1;
int i;
v[++nm]=0,lp[nm]=nm,rp[nm]=nm-1;
for(i=head[x];i!=-1;i=next[i])
{
if(vis[to[i]]) continue;
rp[nm+1]=nm,getd(to[i],x,val[i]);
}
for(i=head[x];i!=-1;i=next[i])
{
if(vis[to[i]]) continue;
tot=siz[to[i]],maxx=1<<30,getr(to[i],x),dfs(root);
}
}
int query(int a,int b)
{
if(a>b) return 0;
int k=Log[b-a+1];
return ms(sm[a][k],sm[b-(1<<k)+1][k]);
}
int main()
{
n=rd(),m=rd();
int i,j,a,b,c,d,x,y;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c);
tot=n,maxx=1<<30,getr(1,0),dfs(root);
for(i=1;i<=nm;i++) sm[i][0]=i;
for(i=2;i<=nm;i++) Log[i]=Log[i>>1]+1;
for(j=1;(1<<j)<nm;j++)
for(i=1;i+(1<<j)-1<=nm;i++)
sm[i][j]=ms(sm[i][j-1],sm[i+(1<<j-1)][j-1]);
for(i=1;i<=nm;i++)
{
if(lp[i]>rp[i]) continue;
pq.push(mp(v[i]+v[query(lp[i],rp[i])],i,lp[i],rp[i]));
}
for(i=1;i<=m;i++)
{
pii t1=pq.top().first,t2=pq.top().second;
pq.pop();
printf("%d
",t1.first),x=t1.second,a=t2.first,b=t2.second,y=query(a,b);
c=query(a,y-1),d=query(y+1,b);
if(c) pq.push(mp(v[x]+v[c],x,a,y-1));
if(d) pq.push(mp(v[x]+v[d],x,y+1,b));
}
return 0;
}