[BZOJ3784]树上的路径（点分治+STL）

题目：

我是超链接

题解：

我用的是二分+点分治的方法
二分m大的路径长度，得到下界以后显然是一个nlog^2n的经典点分治，加上二分的log，显然比较虚。但是点分治中有一个log是sort需要的，我们就可以先一次点分治把sort的结果用vector存下来，这样的话就能把总复杂度降为nlog^2，得到m大的路径最后一次点分治暴力统计路径。总复杂度是O(nlog^2n)的，但不知道是不是map和vector的问题，我常数贼大，然后就T了？！
下面是TLE代码，我觉得复杂度是对的，但是求正解的盆友不要看了。
但是这道题STL的用法很好，所以即使T了还是想着码一下

代码：

#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;
const int N=50005;
const int NN=300005;
int n,tot,nxt[N*2],point[N],v[N*2],c[N*2],size[N],f[N],root,num,k,m,sum,len[N],dis[N],mid,id,game[NN],ans,vis[N],ID;
vector <int> ini[NN]; map<int,int> answer;
void addline(int x,int y,int z)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z;
}
void find(int x,int fa)
{
    size[x]=1;f[x]=0;
    for (int i=point[x];i;i=nxt[i])
      if (vis[v[i]]!=ID && v[i]!=fa)
      {
        find(v[i],x);
        size[x]+=size[v[i]];
        f[x]=max(f[x],size[v[i]]);
      }
    f[x]=max(f[x],sum-f[x]);
    if (f[x]<f[root]) root=x;
}
void dfs(int x,int fa)
{
    len[++num]=dis[x];
    for (int i=point[x];i;i=nxt[i])
      if (v[i]!=fa && vis[v[i]]!=ID)
      {
        dis[v[i]]=dis[x]+c[i];
        dfs(v[i],x);
      }
}
int calc(int x,int nowlen,int sc,int vv)
{
    ++id;
    if (sc==1)//预处理 
    {
        dis[x]=nowlen;num=0;dfs(x,0);
        sort(len+1,len+num+1);
        ini[id].push_back(num);
        for (int i=1;i<=num;i++) ini[id].push_back(len[i]);
        return 0;
    }
    if (sc==2)//二分答案 
    {
        int l=1,r=ini[id][0],sb=0;
        for (;l<r;r--)
        {
            while (l<r && ini[id][l]+ini[id][r]<mid) l++;
            sb+=r-l;
        }
        return sb;
    }
    if (sc==3)//输出
    {
        int l=1,r=ini[id][0];
        for (;l<r;r--)
        {
            while (l<r && ini[id][l]+ini[id][r]<mid) l++;
            for (int i=l;i<r;i++) answer[ini[id][i]+ini[id][r]]+=vv;
        }
        return 0;
    }
}
void work(int x,int sc)
{
    ans+=calc(x,0,sc,1); vis[x]=ID;
    for (int i=point[x];i;i=nxt[i])
      if (vis[v[i]]!=ID)
      {
        ans-=calc(v[i],c[i],sc,-1);
        sum=size[v[i]]; f[0]=INF; root=0; find(v[i],x);
        work(root,sc);
      }
}
int check(int sc)
{
    ans=0;
    sum=n; f[0]=INF; root=0; find(1,0);
    work(root,sc);
    return ans;
}
int main()
{
    int i,l=1,r=0,M;scanf("%d%d",&n,&m);
    for (i=1;i<n;i++)
    {
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        addline(x,y,z);r+=z;
    }
    ID++;check(1);id=0;
    while (l<=r)
    {
        id=0;ID++;
        mid=(l+r)>>1;int t=check(2);//长于mid的有多少 
        if (t<m) r=mid-1;
        else l=mid+1;
        if (t==m) break;
    }
    ID++; id=0; check(3);
    map<int,int>::iterator it;i=0;
    for(it=answer.begin();it!=answer.end();++it)
    {
        int cs=it->second;
        while (cs--) game[++i]=it->first;
    }
    for (i=m;i>=1;i--) printf("%d\n",game[i]);
}