poj1741-Tree

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

题意是给你一棵树，求长度不超过k的路径有多少条

点分治
如果指定节点p作为树的根，那么树上的路径就可以分为两类
1.经过节点p
2.不经过节点p
根据分治的思想，对于第二类路径，显然可以把p的每棵子树作为子问题，递归处理
而对于第一类路径
对于这题，可以对这个点延伸出的几棵子树各做一次dfs记录子树中出现的距离值
对于一棵树的距离值数组，把它排序求一次ans1，再对每棵子树分别求一个自己对自己的ans2，ans1−∑ans2即为最后的ans

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
//#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e5+10;
struct orz{
    int v,nex,s;}e[N*2];
int last[N],son[N],deep[N],f[N],d[N];
int n,k,cnt,root,sum,ans;
bool vis[N];
void add(int x,int y,int z)
{
    cnt++;
    e[cnt].v=y;
    e[cnt].nex=last[x];
    last[x]=cnt;
    e[cnt].s=z;
}
void getroot(int x,int fa) //找重心
{
    son[x]=1; f[x]=0;
    for (int i=last[x];i;i=e[i].nex)
    {
        if (e[i].v==fa || vis[e[i].v]) continue;
        getroot(e[i].v,x);
        son[x]+=son[e[i].v];
        f[x]=max(f[x],son[e[i].v]);
    }
    f[x]=max(f[x],sum-son[x]);
    if (f[x]<f[root]) root=x;
}
void getdeep(int x,int fa) 
{
    deep[++deep[0]]=d[x];
    for (int i=last[x];i;i=e[i].nex)
    {
        if (e[i].v==fa || vis[e[i].v]) continue;
        d[e[i].v]=d[x]+e[i].s;
        getdeep(e[i].v,x);
    }
}
int cal(int x,int now)
{
    d[x]=now; deep[0]=0;
    getdeep(x,0);
    sort(deep+1,deep+deep[0]+1);
    int t=0,l,r;
    for (l=1,r=deep[0];l<r;)
    {
        if (deep[l]+deep[r]<=k)
        {
            t+=r-l; l++;
        }
        else r--;
    }
    return t;
}
void work(int x)
{
    ans+=cal(x,0);
    vis[x]=1;
    for (int i=last[x];i;i=e[i].nex)
    {
        if (vis[e[i].v]) continue;
        ans-=cal(e[i].v,e[i].s);
        sum=son[e[i].v];
        root=0;
        getroot(e[i].v,root);
        work(root);
    }
}
int main()
{
    while (scanf("%d%d",&n,&k)&&(n+k))
    {
        cnt=0; ans=0;
        memset(last,0,sizeof(last));
        memset(vis,0,sizeof(vis));
        int x,y,z;
        for (int i=1;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z); add(y,x,z);
        }
        sum=n; f[0]=inf;
        getroot(1,0);
        work(root);
        printf("%d
",ans);
    }
    return 0;
}

View Code