| WZJ的旅行（五） |
| 难度级别：E； 运行时间限制：3000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
试题描述 |
WZJ又要去旅行了T^T=0。幻想国由N个城市组成，由于道路翻修，只有N-1条双向道路可以通行，第i条双向道路从ui连接到vi，距离为wi。但这N-1条道路竟然连接了整个国家，每两个城市之间都有一条道路！ 设d(a,b)表示a城市到b城市的距离（a<b）。WZJ想知道前k大的d(a,b)的值请你告诉他结果。 |
输入 |
第一个为两个正整数N,k。 接下来N-1行每行为三个正整数ui,vi,wi。 |
输出 |
输出前k大的d(a,b)值，每个一行。 |
输入示例 |
5 10 1 2 1 1 3 2 2 4 3 2 5 4 |
输出示例 |
7 7 6 5 4 4 3 3 2 1 |
其他说明 |
1<=N<=50000,1<=k<=Min(300000,N*(N-1)/2) 1<=ui,vi<=N 1<=wi<=1000 |
题解：点分治套一个超级钢琴耶，先将一个点能够到的位置用l,r数组记录下来（意会一下“够到”。。。），然后问题变为超级钢琴。。。。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<2;d++)if(ch[d])
#define lson x->ch[0],L,M
#define rson x->ch[1],M+1,R
using namespace std;
const int maxn=+,maxnode=+,maxm=+,maxt=maxn*,inf=-1u>>;
struct ted{int x,y,w;ted*nxt;}adj[maxm],*fch[maxn],*ms=adj;
void add(int x,int y,int w){
*ms=(ted){x,y,w,fch[x]};fch[x]=ms++;
*ms=(ted){y,x,w,fch[y]};fch[y]=ms++;
return;
}
int CG,size,siz[maxn],f[maxn],l[maxt],r[maxt],t[maxt],ln,rn,tot;bool vis[maxn];
void findcg(int x,int fa){
siz[x]=;int mxs=;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(v!=fa&&!vis[v]){
findcg(v,x);siz[x]+=siz[v];mxs=max(mxs,siz[v]);
}
}f[x]=max(mxs,size-siz[x]);if(f[x]<f[CG])CG=x;return;
}
void dfs(int x,int fa,int dis){
siz[x]=;l[++tot]=ln;r[tot]=rn;t[tot]=dis;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(v!=fa&&!vis[v])dfs(v,x,dis+e->w),siz[x]+=siz[v];
}return;
}
void solve(int x){
vis[x]=true;bool flag=true;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(!vis[v]){
if(flag)flag=false,ln=rn=++tot;
dfs(v,x,e->w);rn=tot;
}
}
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(!vis[v]){
f[CG=]=size=siz[v];findcg(v,x);solve(CG);
}
}return;
}
struct node{
node*ch[];int p,v;node(){v=-inf;}
void update(){v=-inf;CH{if(v<ch[d]->v)p=ch[d]->p,v=ch[d]->v;}return;}
}seg[maxnode],*nodecnt=seg,*root;int n,k,ql,qr,_p,_v;
void build(node*&x=root,int L=,int R=tot){
x=nodecnt++;int M=L+R>>;if(L==R)x->p=M,x->v=t[M];
else build(lson),build(rson),x->update();return;
}
void query(node*x=root,int L=,int R=tot){
if(ql<=L&&R<=qr){
if(_v<x->v)_v=x->v,_p=x->p;
}else{int M=L+R>>;
if(ql<=M)query(lson);if(qr>M)query(rson);
}return;
}
struct info{int x,L,R,t;};
bool operator<(const info&a,const info&b){return t[a.t]+t[a.x]<t[b.t]+t[b.x];}
priority_queue<info>Q;
inline int read(){
int x=,sig=;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;
for(;isdigit(ch);ch=getchar())x=*x+ch-'';
return sig?x:-x;
}
inline void write(long long x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=;long long buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
void init(){
n=read();k=read();int x,y;
for(int i=;i<n;i++)x=read(),y=read(),add(x,y,read());
f[CG=]=size=n;findcg(,);solve(CG);
build();
for(int i=;i<=tot;i++)if(l[i]){
ql=l[i];qr=r[i];_v=-inf;query();Q.push((info){i,l[i],r[i],_p});
}
for(int i=;i<=k;i++){
info a=Q.top();Q.pop();write(t[a.x]+t[a.t]);ENT;
if(a.L<a.t){ql=a.L;qr=a.t-;_v=-inf;query();Q.push((info){a.x,a.L,a.t-,_p});}
if(a.t<a.R){ql=a.t+;qr=a.R;_v=-inf;query();Q.push((info){a.x,a.t+,a.R,_p});}
}
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}