poj 1741 Tree 树的分治 - c++编程基础

解法论文中有，就是把路径分成经过树根，和不经过树根两类，每次处理经过树根的，然后剩下的子树部分可以递归处理，如果每次选取树的重心，那么可以保证最多递归logn层。经过树根的先排序，然后O(n)的复杂度就能算出，那么每层的复杂度nlogn，最多递归logn层，总复杂度nlogn^2

 
#include   
#include   
#include   
#include   
using namespace std;  
const int maxn=1e4+9;  
int head[maxn],lon;  
bool use[maxn];  
int a[maxn],d[maxn],top,son[maxn];  
int ans,n,m,mm;  
struct  
{  
    int next,to,w;  
}e[maxn<<1];  
  
void edgeini()  
{  
    memset(head,-1,sizeof(head));  
    lon=-1;  
}  
void edgemake(int from,int to,int w)  
{  
    e[++lon].to=to;  
    e[lon].w=w;  
    e[lon].next=head[from];  
    head[from]=lon;  
}  
int maxson[maxn];  
int dp(int t,int from)  
{  
    int now,tmp=1e5,ans;  
    son[t]=maxson[t]=0;  
    for(int k=head[t];k!=-1;k=e[k].next)  
    {  
        int u=e[k].to;  
        if(use[u]||u==from) continue;  
        now=dp(u,t);  
        if(maxson[now]




i&&a[i]+a[now]>m) now--;  
        ret+=now-i;  
    }  
    return ret;  
}  
  
void solve(int t)  
{  
    int now=dp(t,0);  
    d[now]=top=0;  
    use[now]=1;  
    dfs(now,0);  
    int ret=0,tmp=2;  
    for(int k=head[now];k!=-1;k=e[k].next)  
    {  
        int u=e[k].to;  
        if(use[u]) continue;  
        sort(a+tmp,a+tmp+son[u]);  
        ret+=cal(tmp,tmp+son[u]-1);  
        tmp+=son[u];  
    }  
    sort(a+1,a+tmp);  
    ans+=cal(1,tmp-1)-ret;  
//    printf("%d %d\n",now,ans);  
    for(int k=head[now];k!=-1;k=e[k].next)  
    {  
        int u=e[k].to;  
        if(use[u]||son[u]==1) continue;  
        mm=son[u];  
        solve(u);  
    }  
}  
  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    while(scanf("%d %d",&n,&m),n&&m)  
    {  
        edgeini();  
        for(int i=1,from,to,w;i