poj1741 Tree （点分治）

题面（具体题目读者可以参考poj1741）

给一棵有 n 个顶点的树，每条边都有一个长度（小于 1001 的正整数）。
定义 dist(u,v)=节点 u 和 v 之间的最小距离。
给定一个整数 k，对于每一对 (u,v) 顶点当且仅当 dist(u,v) 不超过 k 时才称为有效。
编写一个程序，计算给定树有多少对有效。

输入包含几个测试用例。每个测试用例的第一行包含两个整数 n、k。(n<=10000) 下面的 n-1 行每行包含三个整数 u,v,l，这意味着节点 u 和 v 之间存在一条长度为 l 的边。
最后一个测试用例后跟两个零。

sourse：

首先题目给出一棵无根树（没有明确根节点），所以我们选取树的重心作为划分点root。

树上的路径分为两种：1.经过root；2.不经过root（即两点均在root的一颗子树中），我们只需求解第一类路径，第二类路径根据分治策略继续采用重心分解即可得到。

算法设计：

1.求树的重心root；

2.从root出发，统计每个节点到root的距离d[u]；

3.维护一个距离数组，对其进行排序，双指针扫描，统计满足条件的数量；

4.对root的每一棵子树v都减去重复统计的节点数；

5.从v出发重复上述过程；

size[i]表示以i为根节点的子树大小；f[i]指i的最大子树的节点数；d[i]指i到根的距离；dep：距离数组

#include
#include
#include
using namespace std;
const int maxn=10005;
int cnt,n,k,ans,head[maxn];
int root,S,size[maxn],f[maxn],d[maxn],dep[maxn];
bool vis[maxn];
struct edge{
　　int to,next,w;
}edge[maxn*2];

void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
}

void getroot(int u,int fa)//获取重心
{
    size[u]=1;
    f[u]=0;//删除u后，最大子树的大小 
    for(int i=head[u];i;i=edge[i].next)
    {
    	int v=edge[i].to;
    	if(v!=fa&&!vis[v])
        {
            getroot(v,u);
            size[u]+=size[v];
       	    f[u]=max(f[u],size[v]);
        }
　　 }
    f[u]=max(f[u],S-size[u]);//S为当前子树总结点数 
    if(f[u]　　 }
    return sum;
}

void solve(int u) //获取答案
{
    vis[u]=true;
　　 ans+=getsum(u,0);
    for(int i=head[u];i;i=edge[i].next)
    {
    	int v=edge[i].to;
	if(!vis[v])
	{
	    ans-=getsum(v,edge[i].w);//减去重复
            root=0;
	    S=size[v];
	    getroot(v,u);
            solve(root);
	}
    }
}

int main()
{
    f[0]=0x7fffffff;//初始化树根 
    while(scanf("%d%d",&n,&k),n+k)
    {
        memset(vis,0,sizeof(vis));
	memset(head,0,sizeof(head));
	cnt=0;ans=0;
        for(int i=1;i<=n-1;i++)
        {
            int x,y,z;
	    scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
	    add(y,x,z);
        }
        root=0;
	S=n;
	getroot(1,0);
	solve(root);
        printf("%d\n",ans);
    }
    return 0;
}