spoj1825 Free tour II 点分治

给一颗带权树，这颗树上每个点有一个点色 黑色或白色 现在要求经过不超过K个点的最长路径长度是多少

将无根树转换为有根树，每次只考虑一个点，计算经过该点不超过K个点的最长路径长度。考虑完该点之后把该点删掉。然后从子树中再找一点。一直这样下去。每次找重心。最多有$log_2 n$层，然后每层跑个$O(nlog_2 n)$是可以接受的
要考虑到怎么计算经过该点不超过K个点的最长路径长度。
记录对于点u引出的儿子节点集合假设为$T(u)$
算出对于所有 $v$属于$T(u)$
从$v$走经过最多的黑色点数为$m_v$ 和 从$v$开始走经过$0$个黑点走最远的距离，从$v$开始走经过$1$个黑点走最远的距离，。。。从$v$开始走经过$m_v$个黑点走最远的距离。
如果两两枚举对于该点的两棵子树最大黑点的话会T掉的。
其实不用那么麻烦两两枚举，也不用排序。
只需任意枚举单个，合并，记录结果即可。
因为没有开栈外挂所以一直挂一直挂一直挂。。。。。
（一直RE一直RE一直RE，还有TLE、WA各种都有。。。
代码：

//author: CHC
//First Edit Time:	2015-10-12 15:51
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=200000+100;
const int MAXM=MAXN*2;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Edge {
    int to,next,wi;
    Edge(){}
    Edge(int _to,int _next,int _wi):to(_to),next(_next),wi(_wi){}
}e[MAXM];
int head[MAXN],tot;
void init(){
    memset(head,-1,sizeof(head)); tot=0;
}
void AddEdge(int u,int v,int wi){
    e[tot]=Edge(v,head[u],wi);
    head[u]=tot++;
    e[tot]=Edge(u,head[v],wi);
    head[v]=tot++;
}
int siz[MAXN],ts[MAXN],root;
char vis[MAXN];
void getroot(int u,int fa){
    siz[u]=1;ts[u]=0;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==fa||vis[v])continue;
        getroot(v,u);
        ts[u]=max(ts[u],siz[v]);
        siz[u]+=siz[v];
    }
    ts[u]=max(ts[u],ts[0]-siz[u]);
    if(ts[u]<=ts[root])root=u;
}
int color[MAXN];
int n,m,K; int ans;
int deep[MAXN]; int dis[MAXN],tmp[MAXN],mx[MAXN];
void getdis(int u,int fa){
    deep[0]=max(deep[0],deep[u]);
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==fa||vis[v])continue;
        deep[v]=deep[u]+color[v];
        dis[v]=dis[u]+e[i].wi;
        getdis(v,u);
    }
}
void getmx(int u,int fa){
    tmp[deep[u]]=max(tmp[deep[u]],dis[u]);
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==fa||vis[v])continue;
        getmx(v,u);
    }
}
int mD;
void update(int x,int v){
    if(x==0){
        mx[x]=max(mx[x],v);
        return ;
    }
    for(int i=x;i<=mD;i+=i&-i)mx[i]=max(mx[i],v);
}
int query(int x){
    if(x==0){
        return mx[0];
    }
    int cnt=mx[0];
    for(int i=x;i>0;i-=i&-i)cnt=max(mx[i],cnt);
    return cnt;
}
void cls(){
    memset(mx,0,sizeof(int)*(mD+2));
}
vector < pair<int,int> > st;
void solve(int u){
    vis[u]=1;st.clear();
    mD=0;
    if(color[u])--K;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(vis[v])continue;
        deep[0]=0;deep[v]=color[v];dis[v]=e[i].wi;
        getdis(v,u);
        st.push_back(make_pair(deep[0],v));
        mD=max(mD,deep[0]);
    }
    //sort(st.begin(),st.end());
    int sz=st.size();
    cls();
    for(int i=0;i<sz;i++){
        getmx(st[i].second,u);
        for(int j=min(K,st[i].first);j>=0;j--){
            if(K-j>mD) ans=max(ans,tmp[j]+query(mD));
            else ans=max(ans,tmp[j]+query(K-j));
        }
        for(int j=0;j<=st[i].first;j++){
            update(j,tmp[j]);
            tmp[j]=0;
            //if(i==sz-1)mx[j]=0;
        }
    }
    //ans=max(ans,query(mD));
    if(color[u])++K;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(vis[v])continue;
        root=0;ts[0]=siz[v];
        getroot(v,u);
        solve(root);
    }
}
int main()
{
    int size = 256 << 20; // 256MB  
    char *p = (char*)malloc(size) + size;  
    __asm__("movl %0, %%esp\n" :: "r"(p));
    while(~scanf("%d%d%d",&n,&K,&m)){
        memset(color,0,sizeof(color));
        memset(tmp,0,sizeof(tmp));
        memset(mx,0,sizeof(mx));
        memset(vis,0,sizeof(vis));
        for(int i=0,x;i<m;i++){
            scanf("%d",&x);
            color[x]=1;
        }
        init();
        for(int i=0,x,y,wi;i<n-1;i++){
            scanf("%d%d%d",&x,&y,&wi);
            AddEdge(x,y,wi);
        }
        root=0;ts[0]=n;
        getroot(1,1);
        ans=0;solve(root);
        printf("%d\n",ans);
    }
    return 0;
}
/*
   8 2 3
   3
   5
   7
   1 3 1
   2 3 10
   3 4 -2
   4 5 -1
   5 7 6
   5 6 5
   4 8 3
   7 5 6 
   2 
   3 
   4 
   5 
   6 
   7 
   1 7 100 
   1 5 100 
   5 6 100 
   1 2 1 
   2 3 1 
   3 4 1
   5 3 4 
   2 
   3 
   4 
   5 
   1 2 1 
   2 3 3 
   1 4 1 
   1 5 2 
   */