题意分析

Boatherds公司运营的航海网络由多个村庄和连接它们的河流组成，村庄和河流构成一棵树。每条河流都有一个价格，游客在两个村庄之间的旅行费用是路径上所有河流价格的总和。给定多个查询，每个查询给出一个金额$x_i$，问是否存在两个村庄之间的旅行费用恰好等于$x_i$。

解题思路

本题需要高效处理树上的路径查询问题，核心是判断是否存在路径长度等于给定值$x_i$。直接暴力枚举所有路径显然不可行，因为时间复杂度为$O(N^2)$，对于$N=10,000$来说无法承受。

点分治算法

点分治（Divide and Conquer on Tree）是解决树上路径问题的经典算法，其核心思想是通过选取树的重心递归分解问题，将问题规模缩小到子树中处理，从而将时间复杂度优化到$O(N \log N)$。

1. 找重心：每次处理当前子树时，找到其重心作为根节点，将问题分解为子问题。
2. 计算路径：以重心为根，计算所有经过重心的路径长度，并统计满足条件的路径数量。
3. 去重：减去同一子树内重复计算的路径（因为这些路径实际上不经过重心）。
4. 递归处理子树：对每个子树重复上述过程。

具体步骤

1. 重心分解：

   • 计算子树大小$s[u]$和最大子树大小$f[u]$。
   • 重心是使$f[u]$最小的节点，确保每次分割后子树大小均衡。

2. 路径计算：

   • 对于当前重心$root$，计算所有从$root$出发的路径长度$dep$。
   • 对$dep$排序后，使用双指针法统计满足$dep[l] + dep[r] = x_i$的路径对数。

3. 去重处理：

   • 对于每个子树，单独计算其内部路径长度，并从总和中减去这些路径（因为它们被重复计算）。

4. 递归处理：

   • 对$root$的每个子树递归处理，直到所有子树处理完毕。

时间复杂度

每次递归处理的时间复杂度为$O(N \log N)$，总时间复杂度为$O(N \log^2 N)$，能够高效处理大规模数据。

标程

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

struct Node {
    int v, l;
    Node() : v(0), l(0) {}
    Node(int _v, int _l) : v(_v), l(_l) {}
};

const int N = 10015;

class TreeSolver {
private:
    int n, K, size, root, ans;
    int s[N], f[N], d[N];
    bool done[N];
    vector<int> dep;
    vector<Node> g[N];

    void getRoot(int now, int fa) {
        s[now] = 1;
        f[now] = 0;
        
        for (size_t i = 0; i < g[now].size(); i++) {
            int u = g[now][i].v;
            if (u != fa && !done[u]) {
                getRoot(u, now);
                s[now] += s[u];
                f[now] = max(f[now], s[u]);
            }
        }
        
        f[now] = max(f[now], size - s[now]);
        if (f[now] < f[root]) {
            root = now;
        }
    }

    void getDep(int now, int fa) {
        dep.push_back(d[now]);
        s[now] = 1;
        
        for (size_t i = 0; i < g[now].size(); i++) {
            int u = g[now][i].v;
            if (u != fa && !done[u]) {
                d[u] = d[now] + g[now][i].l;
                getDep(u, now);
                s[now] += s[u];
            }
        }
    }

    int calc(int now, int init) {
        d[now] = init;
        dep.clear();
        getDep(now, 0);
        sort(dep.begin(), dep.end());
        
        int ret = 0;
        int l = 0, r = dep.size() - 1;
        
        while (l < r) {
            int sum = dep[l] + dep[r];
            if (sum == K) {
                if (dep[l] == dep[r]) {
                    ret += (r - l + 1) * (r - l) / 2;
                    break;
                }
                
                int i = l, j = r;
                while (dep[i] == dep[l]) i++;
                while (dep[j] == dep[r]) j--;
                
                ret += (i - l) * (r - j);
                l = i;
                r = j;
            } 
            else if (sum < K) {
                l++;
            }
            else {
                r--;
            }
        }
        
        return ret;
    }

    void work(int now) {
        ans += calc(now, 0);
        done[now] = true;
        
        for (size_t i = 0; i < g[now].size(); i++) {
            int u = g[now][i].v;
            if (!done[u]) {
                ans -= calc(u, g[now][i].l);
                f[0] = size = s[u];
                getRoot(u, root = 0);
                work(root);
            }
        }
    }

public:
    void solve() {
        memset(done, false, sizeof(done));
        f[0] = size = n;
        getRoot(1, root = 0);
        ans = 0;
        work(root);
        cout << (ans ? "AYE" : "NAY") << endl;
    }

    void readInput() {
        while (cin >> n && n) {
            for (int i = 0; i <= n; i++) {
                g[i].clear();
            }
            
            int a, b;
            for (int i = 1; i <= n; i++) {
                while (cin >> a && a) {
                    cin >> b;
                    g[i].push_back(Node(a, b));
                    g[a].push_back(Node(i, b));
                }
            }
            
            while (cin >> K && K) {
                solve();
            }
            cout << "." << endl;
        }
    }
};

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    TreeSolver solver;
    solver.readInput();

    return 0;
}