[bzoj3784]树上的路径

点分治，当一个节点作为重心时，统计出：1.每一个点的深度；2.每一个点所能选择的路径对应点区间，可以发现这样的点数只需要nlogn。然后类似于bzoj2006超级钢琴的堆+线段树来做即可。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 50005
  4 #define L (k<<1)
  5 #define R (L+1)
  6 #define mid (l+r>>1)
  7 struct ji{
  8     int nex,to,len;
  9 }edge[N<<1];
 10 int E,r,n,m,x,y,z,tot,s[N*20],sz[N],head[N],vis[N],f[N*80];
 11 struct ji2{
 12     int l,r;
 13 }a[N*20];
 14 struct ji3{
 15     int k,l,r,mx;
 16     bool operator < (const ji3 &t)const{
 17         return s[k]+s[mx]<s[t.k]+s[t.mx];
 18     }
 19 };
 20 priority_queue<ji3>q;
 21 int up(int x,int y){
 22     if (s[x]>s[y])return x;
 23     return y;
 24 }
 25 void update(int k,int l,int r,int x){
 26     if (l==r){
 27         f[k]=l;
 28         return;
 29     }
 30     if (x<=mid)update(L,l,mid,x);
 31     else update(R,mid+1,r,x);
 32     f[k]=up(f[L],f[R]);
 33 }
 34 int query(int k,int l,int r,int x,int y){
 35     if ((l>y)||(x>r))return 0;
 36     if ((x<=l)&&(r<=y))return f[k];
 37     return up(query(L,l,mid,x,y),query(R,mid+1,r,x,y));
 38 }
 39 void add(int k,int x,int y){
 40     q.push(ji3{k,x,y,query(1,1,tot,x,y)});
 41 }
 42 void add_edge(int x,int y,int z){
 43     edge[E].nex=head[x];
 44     edge[E].to=y;
 45     edge[E].len=z;
 46     head[x]=E++;
 47 }
 48 void size(int k,int fa){
 49     sz[k]=1;
 50     for(int i=head[k];i!=-1;i=edge[i].nex)
 51         if ((!vis[edge[i].to])&&(edge[i].to!=fa)){
 52             size(edge[i].to,k);
 53             sz[k]+=sz[edge[i].to];
 54         }
 55 }
 56 void find(int k,int fa,int s){
 57     int t=s-sz[k];
 58     for(int i=head[k];i!=-1;i=edge[i].nex)
 59         if ((!vis[edge[i].to])&&(edge[i].to!=fa)){
 60             find(edge[i].to,k,s);
 61             t=max(t,sz[edge[i].to]);
 62         }
 63     if (t<=s/2)r=k;
 64 }
 65 void calc(int k,int fa,int sh){
 66     if (fa)a[++tot]=ji2{x,y};
 67     else a[x=y=++tot]=ji2{0,0};
 68     s[tot]=sh;
 69     for(int i=head[k];i!=-1;i=edge[i].nex)
 70         if ((!vis[edge[i].to])&&(edge[i].to!=fa)){
 71             calc(edge[i].to,k,sh+edge[i].len);
 72             if (!fa)y=tot;
 73         }
 74 }
 75 void dfs(int k){
 76     size(k,0);
 77     find(k,0,sz[k]);
 78     calc(k=r,0,0);
 79     vis[k]=1;
 80     for(int i=head[k];i!=-1;i=edge[i].nex)
 81         if (!vis[edge[i].to])dfs(edge[i].to);
 82 }
 83 int main(){
 84     scanf("%d%d",&n,&m);
 85     memset(head,-1,sizeof(head));
 86     for(int i=1;i<n;i++){
 87         scanf("%d%d%d",&x,&y,&z);
 88         add_edge(x,y,z);
 89         add_edge(y,x,z);
 90     }
 91     dfs(1);
 92     s[0]=-0x3f3f3f3f;
 93     for(int i=1;i<=tot;i++)update(1,1,tot,i);
 94     for(int i=1;i<=tot;i++)add(i,a[i].l,a[i].r);
 95     for(int i=1;i<=m;i++){
 96         ji3 o=q.top();
 97         q.pop();
 98         printf("%d\n",s[o.k]+s[o.mx]);
 99         if (o.l<o.mx)add(o.k,o.l,o.mx-1);
100         if (o.mx<o.r)add(o.k,o.mx+1,o.r);
101     }
102 }