题意分析

题目描述： Farmer John 希望知道有多少对农场之间的距离不超过给定的整数 K。距离定义为两个农场之间路径上所有道路的总长度。需要注意的是，农场对 (u, v) 和 (v, u) 被视为同一对，且不能与自身配对（即不考虑 (u, u) 的情况）。

输入格式：

• 前 M+1 行：与“Navigation Nightmare”相同的输入格式，即农场的数量 n 和道路的数量 q，随后 q 行描述道路，每行格式为 x y w c（x 和 y 是道路连接的两个农场编号，w 是道路的长度，c 是可以忽略的字符）。
• 第 M+2 行：一个整数 K，表示距离阈值。

输出格式：

• 一行：距离不超过 K 的农场对的数量。

解题思路

问题建模： 这是一个典型的树中距离问题，需要统计树中所有距离不超过 K 的节点对的数量。可以通过点分治（Centroid Decomposition）算法高效解决。

点分治算法步骤：

1. 找重心：选择当前树的重心作为根节点，重心是指删除该节点后，剩余子树的最大节点数最小的节点。
2. 计算深度：从重心出发，计算所有节点到重心的距离，并排序。
3. 统计答案：使用双指针法统计距离不超过 K 的节点对数量。
4. 递归处理子树：对重心连接的每个子树递归处理，避免重复计算。

代码实现

#include <iostream>
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>

#define LL long long
#define INF 0x3f3f3f3f
#define Mod  1000000007
#define Seed1 31
#define Seed2 37
#define EPS (1e-8)

using namespace std;

const int MAXE = 80010;
const int MAXP = 40010;

struct EDGE
{
    int v, w, next;
} edge[MAXE];
int head[MAXP];
int Top;

void Link(int u, int v, int w)
{
    edge[Top].w = w;
    edge[Top].v = v;
    edge[Top].next = head[u];
    head[u] = Top++;
}

int PointNum[MAXP];
int MaxPointNum[MAXP];
bool STOP[MAXP]; // 递归时控制边界
int depth[MAXP];
int S[MAXP];
int tot;

void InitGraph()
{
    memset(STOP, false, sizeof(STOP));
    memset(head, -1, sizeof(head));
    Top = 0;
}

int getPointNum(int s, int pre)
{
    PointNum[s] = 1;

    for (int i = head[s]; i != -1; i = edge[i].next)
    {
        if (STOP[edge[i].v] || edge[i].v == pre)
            continue;
        PointNum[s] += getPointNum(edge[i].v, s);
    }
    return PointNum[s];
}

void getMaxPointNum(int s, int pre, int n, int &Min, int &gc)
{
    int Max = n - PointNum[s];

    for (int i = head[s]; i != -1; i = edge[i].next)
    {
        if (STOP[edge[i].v] || edge[i].v == pre)
            continue;

        Max = max(Max, PointNum[edge[i].v]);

        getMaxPointNum(edge[i].v, s, n, Min, gc);
    }

    if (Min > Max)
        Min = Max, gc = s;
}

int getGC(int s, int n)
{
    getPointNum(s, -1);
    int Min = n, gc = s;
    getMaxPointNum(s, -1, n, Min, gc);
    return gc;
}

void getDepth(int s, int pre, int len)
{
    S[++tot] = len;
    depth[s] = len;

    for (int i = head[s]; i != -1; i = edge[i].next)
    {
        if (STOP[edge[i].v] || edge[i].v == pre)
            continue;

        getDepth(edge[i].v, s, len + edge[i].w);
    }
}

int getAns(int k)
{
    sort(S + 1, S + tot + 1);

    int ans = 0;

    int L = 1, R = tot;

    while (L < R)
    {
        if (S[L] <= k - S[R])
            ans += R - L, ++L;
        else
            R--;
    }
    return ans;
}

int dfs(int s, int n, int k)
{
    int gc = getGC(s, n);

    tot = 0;
    getDepth(gc, -1, 0);

    int ans = getAns(k);

    for (int i = head[gc]; i != -1; i = edge[i].next)
    {
        if (STOP[edge[i].v])
            continue;
        tot = 0;
        getDepth(edge[i].v, gc, edge[i].w);
        ans -= getAns(k);
    }

    STOP[gc] = true;

    for (int i = head[gc]; i != -1; i = edge[i].next)
    {
        if (STOP[edge[i].v])
            continue;
        ans += dfs(edge[i].v, PointNum[edge[i].v], k);
    }

    return ans;
}

int main()
{
    int n, m, u, v, w, i, j, k;
    char dir[4];

    while (scanf("%d %d", &n, &m) != EOF)
    {
        InitGraph();
        for (i = 1; i <= m; ++i)
        {
            scanf("%d %d %d %s", &u, &v, &w, dir);
            Link(u, v, w);
            Link(v, u, w);
        }

        scanf("%d", &k);

        printf("%d\n", dfs(1, n, k));
    }

    return 0;
}