BZOJ_3365_[Usaco2004 Feb]Distance Statistics 路程统计&&POJ_1741_Tree_点分治

Description

在得知了自己农场的完整地图后（地图形式如前三题所述），约翰又有了新的问题．他提供

一个整数K(1≤K≤109)，希望你输出有多少对农场之间的距离是不超过K的．

Input

第1到I+M行：与前三题相同；

第M+2行：一个整数K.

Output

农场之间的距离不超过K的对数．

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

有五对道路之间的距离小于10
1-4,距离为3
4-7,距离为2
1-7,距离为5
3-5,距离为7
3-6,距离为9

点分治，经常用来统计树上路径问题。

每次分治时只考虑经过根的路径，处理出子树里所有点到根的距离，排个序双指针扫一遍。

但是这两个点不可以在根的同一个儿子的子树里，我们强制让他在同一个儿子里跑一下再减掉这个即可。

避免分治层数过多，每次都要找一遍重心，siz也要重新求。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 40050

int head[N],to[N<<1],nxt[N<<1],val[N<<1],d[N],cnt,a[N],n;

int ans,siz[N],dep[N],f[N],root,sum,k;

bool used[N];

inline void add(int u,int v,int w) {

    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;

}

void get_root(int x,int y) {

    siz[x]=1; f[x]=0;

    int i;

    for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]) {

        get_root(to[i],x);

        siz[x]+=siz[to[i]];

        f[x]=max(f[x],siz[to[i]]);

    }

    f[x]=max(f[x],sum-siz[x]);

    if(f[x]<f[root]) root=x;

}

void get_dep(int x,int y) {

    a[++a[0]]=d[x];

    siz[x]=1;

    int i;

    for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]) {

        d[to[i]]=d[x]+val[i];

        get_dep(to[i],x);

        siz[x]+=siz[to[i]];

    }

}

int get_ans(int x,int now) {

    d[x]=now;

    a[0]=0;

    get_dep(x,0);

    sort(a+1,a+a[0]+1);

    int i=1,j=a[0],tmp=0;

    while(i<=a[0]&&i<j) {

        if(a[i]+a[j]<=k) tmp+=j-i,i++;

        else j--;

    }

    return tmp;

}

void work(int x) {

    used[x]=1;

    ans+=get_ans(root,0);

    int i;

    for(i=head[x];i;i=nxt[i]) if(!used[to[i]]) {

        ans-=get_ans(to[i],val[i]);

        root=0;

        sum=siz[to[i]];

        get_root(to[i],0);

        work(root);

    }

}

int main() {

    scanf("%d%*d",&n);

    int i,x,y,z;

    for(i=1;i<n;i++) {

        scanf("%d%d%d%*s",&x,&y,&z);

        add(x,y,z); add(y,x,z);

    }

    scanf("%d",&k);

    f[0]=10000000;

    sum=n;

    root=0;

    get_root(1,0);

    work(root);

    printf("%d\n",ans);

}