poj 1741 树的分治

题目连接
转载博客:http://blog.csdn.net/u010660276/article/details/44920725

题意：在一棵树上找点对数，使得两点之间的距离小于等于k，问有多少对

思想：

找其树的重心，重心即：使得子树个数尽量多，并且子树的结点数尽量少，通俗一点，可以认为就是找个点可以来尽量均分这棵树。

求出重心到每个点的距离，用dis数组表示到其距离，然后求出来后对距离进行排序使得dis[i]+dis[j]<=k,i和j分别从头尾取，更新j之后在更新i

具体内容在代码中体现。

《分治算法在树的路径问题中的应用》(https://wenku.baidu.com/view/8861df38376baf1ffc4fada8.html?re=view)

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn = 10010;
int N,K;
int ans,root,Max;
struct node{
    int v,next,w;
}edge[maxn*2]; 
int head[maxn],tot;//用于遍历 
int maxv[maxn];//树的大小 
int size[maxn];//最大孩子节点size 
int vis[maxn];
int dis[maxn];
int num;
void init()
{
    tot=0;ans=0;
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
}
void add(int u,int v,int w)
{
    edge[tot].v=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}
//处理子树大小 
void dfssize(int u,int f)
{
    size[u]=1;
    maxv[u]=0;
    for(int i=head[u];i!=-1;i=edge[i].next)//新的遍历方法 
    {
        int v=edge[i].v;
        if(v==f||vis[v]) continue;
        dfssize(v,u);
        size[u]+=size[v];//递归求子树大小，返回时加上去 
        if(size[v]>maxv[u]) maxv[u]=size[v];//更新最大子树结点个数 
    }
}
//找重心 
void dfsroot(int r,int u,int f)
{
    if(size[r]-size[u]>maxv[u])//尽量平衡 
    {
        maxv[u]=size[r]-size[u];
    }
    if(maxv[u]<Max) Max=maxv[u],root=u;//条件：最多子树然后，使得每个子树结点大小最小 找根
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f||vis[v]) continue;
        dfsroot(r,v,u);
    }
}

//求每个点离重心的距离
void dfsdis(int u,int d,int f)
{
    dis[num++]=d;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v!=f&&!vis[v])
            dfsdis(v,d+edge[i].w,u);
    }
} 

//计算以u为根的子树有多少点对的距离小于等于k
int calc(int u,int d)
{
    int ret=0;
    num=0;
    dfsdis(u,d,0);
    sort(dis,dis+num);//排序 
    int i=0,j=num-1;//从两头开始 
    while(i<j)//缩减时间使时间变成O(n) 
    {
        while(dis[i]+dis[j]>K&&i<j) j--;
        ret+=j-i;   
        i++;
    } 
    return ret;
} 

void dfs(int u)//对每个点去搜索可能性 
{
    Max = N;
    dfssize(u,0);//子树大小 
    dfsroot(u,u,0);//找根 
    ans+=calc(root,0); 
    vis[root]=1;
    for(int i=head[root];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(!vis[v])
        {
            ans-=calc(v,edge[i].w); 
            dfs(v);
        }
    }
}

int main()
{
    while(scanf("%d%d",&N,&K)!=EOF)
    {
        if(!N&&!K) break;
        int u,v,w;
        init();
        for(int i=1;i<N;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1);
        printf("%d\n",ans); 
    }
    return 0;
}