问题分析

我们需要在一棵树上找到权值最小的路径，路径权值定义为路径上所有节点点权的乘积除以路径长度（节点数）。由于点权和路径长度的范围较大，直接枚举所有路径不现实，需利用树的性质和数学优化方法。

算法思路

$1$. 单节点路径：首先考虑长度为1的路径（单个节点），其权值为自身点权，这是初始候选最小值。 2. 双节点路径：长度为2的路径，权值为两点权乘积除以2，需与单节点路径比较。 3. 长路径分析：对于长度≥3的路径，由于点权≥1，当路径长度增加时，乘积增长速度远慢于分母（长度）的增长速度，因此长路径的权值通常不会更小。可通过数学推导证明，只需枚举所有长度≤2的路径即可找到最小值。

实现步骤

$1$. 读取输入，构建树结构（本题无需显式构建树，只需处理节点点权）。 2. 计算所有单节点路径的权值（即各节点点权本身）。 3. 计算所有双节点路径的权值（两点点权乘积除以2）。 4. 比较所有候选值，找到最小值，以最简分数形式输出。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <numeric> // 用于gcd

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> edges(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }

    vector<long long> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }

    long long min_num = LLONG_MAX;
    long long min_den = 1;

    // 处理单节点路径
    for (long long num : x) {
        if (num < min_num) {
            min_num = num;
            min_den = 1;
        }
    }

    // 处理双节点路径
    for (int i = 1; i <= n; ++i) {
        for (int j : edges[i]) {
            if (j > i) { // 避免重复计算
                long long product = x[i - 1] * x[j - 1];
                long long current_num = product;
                long long current_den = 2;

                // 计算最大公约数并化简分数
                long long g = gcd(current_num, current_den);
                current_num /= g;
                current_den /= g;

                // 比较分数大小：a/b < c/d 等价于 a*d < c*b（避免浮点数误差）
                if (current_num * min_den < min_num * current_den) {
                    min_num = current_num;
                    min_den = current_den;
                }
            }
        }
    }

    cout << min_num << "/" << min_den << endl;

    return 0;
}

算法标签

• 树结构：问题基于树的路径，利用树的无环性分析路径特性。
• 数学优化：通过分析路径长度与点权乘积的增长关系，缩小枚举范围，避免不必要的计算。
• 枚举法：在合理范围内枚举所有可能的候选路径（长度1和2），确保找到最小值。