BZOJ 3365 Distance Statistics [点分治]

今天在复习题目,翻到了这道题,拿来看看,貌似是道点分治,复习一波。

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

5

Hint

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

Solution

点分治,注意细节!
找重心的时候要记得考虑父节点的siz啊!!!

Code

#include <cstdio>  
#include <algorithm>  
  
using namespace std;  
  
const int maxn = 56789;  
const int INF = 1000000007;  
  
int getint()  
{  
    int r = 0, k = 1;  
    char c;  
    for (c = getchar(); c < '0' || c > '9'; c = getchar() ) if (c == '-') k = -1;  
    for (; '0' <= c && c <= '9'; c = getchar() ) r = r * 10 - '0' + c;  
    return r * k;  
}  
  
int n, m, k;  
int h[maxn], siz[maxn];  
  
struct edge_type  
{  
    int v, next, w;  
    bool baned;  
} edge[maxn * 2]; int tote = 0;  
  
void ins(int u, int v, int w)  
{  
    edge[++tote].v = v;  
    edge[tote].next = h[u];  
    edge[tote].w = w;  
    edge[tote].baned = false;  
    h[u] = tote;  
}  
  
int fgans, fgsiz;  
  
void get_fgans(int now, int fa, int size) {  
    int tmp = 1;  
    siz[now] = 1;  
    for (int i = h[now]; i; i = edge[i].next) {  
        if (!edge[i].baned && fa != edge[i].v) {  
            get_fgans(edge[i].v, now, size);  
            siz[now] += siz[edge[i].v];  
            if (tmp < siz[edge[i].v]) tmp = siz[edge[i].v];  
        }  
    }  
    if (tmp < size - siz[now]) tmp = size - siz[now];  
    if (tmp < fgsiz) {  
        fgans = now;  
        fgsiz = tmp;  
    }  
}  
int find_gravity(int rt, int size) {  
    fgsiz = INF;  
    fgans = rt;  
    get_fgans(rt, -1, size);  
    return fgans;  
}  
  
int dis[maxn];  
int zhan[maxn], zcnt;  
  
void get_dis(int now, int nd, int fa) {  
    dis[now] = nd;  
    for (int i = h[now]; i; i = edge[i].next)  
        if (!edge[i].baned && fa != edge[i].v)  
            get_dis(edge[i].v, nd + edge[i].w, now);  
}  
  
void dfs(int now, int fa) {  
    zhan[++zcnt] = dis[now];  
    for (int i = h[now]; i; i = edge[i].next)  
        if (!edge[i].baned && fa != edge[i].v)  
            dfs(edge[i].v, now);  
}  
  
int calculate(int rt) {  
    int ret = 0;  
    zcnt = 0;  
    dfs(rt, -1);  
    sort(zhan + 1, zhan + zcnt + 1);  
    for (int i = 1, j = zcnt; i <= zcnt; ++i) {  
        for (; j && zhan[i] + zhan[j] > k; --j);  
        ret += j;  
    }  
    return ret;  
}  
  
int Ans = 0;  
  
void dfz(int now, int size)  
{  
    int rt = find_gravity(now, size);  
    get_dis(rt, 0, -1);  
    Ans += calculate(rt);  
    int v;  
    for (int i = h[rt]; i; i = edge[i].next)  
        if (!edge[i].baned) {  
            edge[i].baned = edge[((i-1)^1)+1].baned = true;  
            Ans -= calculate(edge[i].v);  
            dfz(edge[i].v, siz[edge[i].v]);  
        }  
}  
  
int main()  
{  
    n = getint();  
    m = getint();  
    int u, v, w;  
    for (int i = 1; i < n; ++i)  
    {  
        u = getint();  
        v = getint();  
        w = getint();  
        ins (u, v, w);  
        ins (v, u, w);  
    }  
    k = getint();  
    dfz(1, n);  
    printf("%d", (Ans - n >> 1));  
    return 0;  
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据