POJ 题目1987 Distance Statistics（树的点分治）

Distance Statistics

Time Limit: 2000MS	Memory Limit: 64000K
Total Submissions: 1973	Accepted: 658
Case Time Limit: 1000MS

Description

Frustrated at the number of distance queries required to find a reasonable route for his cow marathon, FJ decides to ask queries from which he can learn more information. Specifically, he supplies an integer K (1 <= K <= 1,000,000,000) and wants to know how many pairs of farms lie at a distance at most K from each other (distance is measured in terms of the length of road required to travel from one farm to another). Please only count pairs of distinct farms (i.e. do not count pairs such as (farm #5, farm #5) in your answer).

Input

* Lines 1 ..M+1: Same input format as in "Navigation Nightmare"

* Line M+2: A single integer, K.

Output

* Line 1: The number of pairs of farms that are at a distance of at most K from each-other.

Sample Input

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
10
      

Sample Output

5
      

Hint

There are 5 roads with length smaller or equal than 10, namely 1-4 (3), 4-7 (2), 1-7 (5), 3-5 (7) and 3-6 (9).

Source

USACO 2004 February

poj1747买一送一的题。。。

ac代码

14792959

kxh1995

1987

Accepted

3908K

297MS

C++

2393B

2015-10-08 09:11:56

#include<stdio.h>   
#include<string.h>   
#include<algorithm>   
#include<iostream>   
#define max(a,b) (a>b?a:b)   
using namespace std;  
#define N 100100   
int head[N],cnt,pre[N],sum,son[N],vis[N],deep[N],root,dis[N];  
#define INF 0x3f3f3f3f   
int n,m,ans,k;  
struct s  
{  
    int u,v,next,w;  
}edge[N<<1];  
void add(int u,int v,int w)  
{  
    edge[cnt].u=u;  
    edge[cnt].v=v;  
    edge[cnt].w=w;  
    edge[cnt].next=head[u];  
    head[u]=cnt++;  
}  
void get_root(int u,int fa)  
{  
    son[u]=1;  
    pre[u]=0;  
    int i;  
    for(i=head[u];i!=-1;i=edge[i].next)  
    {  
        int v=edge[i].v;  
        if(v==fa||vis[v])  
            continue;  
        get_root(v,u);  
        son[u]+=son[v];  
        pre[u]=max(pre[u],son[v]);  
    }  
    pre[u]=max(pre[u],sum-son[u]);  
    if(pre[u]<pre[root])  
        root=u;  
}  
void get_deep(int u,int fa)  
{  
    deep[++deep[0]]=dis[u];  
    int i;  
    for(i=head[u];i!=-1;i=edge[i].next)  
    {  
        int v=edge[i].v;  
        if(v==fa||vis[v])  
            continue;  
        dis[v]=dis[u]+edge[i].w;  
        get_deep(v,u);  
    }  
}  
int get_sum(int x,int now)  
{  
    dis[x]=now;  
    deep[0]=0;  
    get_deep(x,0);  
    sort(deep+1,deep+1+deep[0]);  
    int res=0,l,r;  
    for(l=1,r=deep[0];l<r;)  
    {  
        if(deep[l]+deep[r]<=k)  
        {  
            res+=(r-l);  
            l++;  
        }  
        else  
            r--;  
    }  
    return res;  
}  
void work(int x)  
{  
    ans+=get_sum(x,0);  
    vis[x]=1;  
    int i;  
    for(i=head[x];i!=-1;i=edge[i].next)  
    {  
        int v=edge[i].v;  
        if(vis[v])  
            continue;  
        ans-=get_sum(v,edge[i].w);  
        sum=son[v];  
        root=0;  
        get_root(v,root);  
        work(root);  
    }  
}  
int main()    
{  
    //int n,m;   
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        int i;  
        cnt=0;   
        memset(head,-1,sizeof(head));  
        for(i=0;i<m;i++)  
        {  
            int u,v,w;  
			char str[5];
            scanf("%d%d%d%s",&u,&v,&w,str);  
            add(u,v,w);  
            add(v,u,w);  
        }  
		scanf("%d",&k);
        sum=n;  
        pre[0]=INF;  
        memset(vis,0,sizeof(vis));  
        root=0;  
        get_root(1,0);  
        ans=0;  
        work(root);  
        printf("%d\n",ans);  
    }  
}