P8602 [蓝桥杯 2013 省 A] 大臣的旅费

题目描述

很久以前，T 王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J 是 T 国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了 J 最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的 J 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第 $x - 1$ 千米到第 $x$ 千米这一千米中（ $x$ 是整数），他花费的路费是 $x + 10$ 这么多。也就是说走 $1$ 千米花费 $11$ ，走 $2$ 千米要花费 $23$ 。

J 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入格式

输入的第一行包含一个整数 $n (n \leq 1 0^{5})$ ，表示包括首都在内的 $T$ 王国的城市数。

城市从 $1$ 开始依次编号， $1$ 号城市为首都。

接下来 $n - 1$ 行，描述 $T$ 国的高速路（ $T$ 国的高速路一定是 $n - 1$ 条）。

每行三个整数 $P_{i}, Q, D_{i}$ ，表示城市 $P_{i}$ 和城市 $Q_{i}$ 之间有一条高速路，长度为 $D_{i} (D_{i} \leq 1000)$ 千米。

输出格式

输出一个整数，表示大臣J最多花费的路费是多少。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

样例解释：大臣 J 从城市 $4$ 到城市 $5$ 要花费 $135$ 的路费。

时限 5 秒, 64M。蓝桥杯 2013 年第四届省赛

解析

总体来看，这道题目的意图是求取树的直径，最多的旅费，那肯定对应着最远的距离，所以来拆分一下这道题目：1.找到两个距离最远的点，2.计算这两个点的旅费

旅费来看是等差数列，第x千米花费x+10元，那么这就是一个等差数列求和：

C os t = \frac{( 首项 + 末项 ) \times 项数}{2} = \frac{( 11 + L + 10 ) \times L}{2}

接下来，就是求树的直径，我们通过两次DFS或者树形DP求解。

两次DFS：因为任何一个大城市都能从首都直接或者通过其他大城市间接到达，所以：

从任意一点出发，比如首都1，找到距离首都最远的城市
然后再从P出发，找到距离P最远的城市Q
那么P到Q的距离就是树的直径L

树形 DP：对于每一个节点 $u$ ，我们寻找以 $u$ 为最高点（转折点）的最长路径。

设 $d_{1} [u]$ 为从节点 $u$ 出发，在其子树中能够到达的最远距离。
设 $d_{2} [u]$ 为从节点 $u$ 出发，在其子树中能够到达的次远距离。
那么，经过节点 $u$ 的最长路径长度就是 $d_{1} [u] + d_{2} [u]$ 。
我们遍历所有节点，其中最大的 $d_{1} [u] + d_{2} [u]$ 就是整棵树的直径 $L$ 。

废话少说，上代码：

代码

两次DFS

//
// Created by 23264 on 2026/1/27.
//
#include<bits/stdc++.h>
using namespace std;
 
struct Edge
{
    int to;
    int weight;
};
 
int n;
vector<vector<Edge>> Road;
int maxx;
int far;
 
void dfs(int u,int p,long long d)
{
    if (d > maxx)
    {
        maxx = d;
        far = u;
    }
    for (auto edge : Road[u])
    {
        if (edge.to != p)
        {
            dfs(edge.to,u,d + edge.weight);
        }
    }
}
 
int main()
{
    cin >> n;
    Road.resize(n + 1);
    for (int i = 0;i < n - 1;i++)
    {
        int Pi,Qi,Di;
        cin >> Pi >> Qi >> Di;
        Road[Pi].push_back({Qi,Di});
        Road[Qi].push_back({Pi,Di});
    }
    maxx = -1;
    dfs(1,-1,0);
    maxx = -1;
    dfs(far,-1,0);
    cout << maxx * 10 + maxx * (maxx + 1) / 2 << endl;
}

树形DP

//
// Created by 23264 on 2026/1/27.
//
#include <bits/stdc++.h>
using namespace std;
 
struct Edge
{
    int to;
    int weight;
};
 
int n;
vector<vector<Edge>> adj;
long long d1[100005];// 第一长路径
long long d2[100005];// 第二长路径
long long maxx = 0;// 最大直径
 
void DP(int u,int p)
{
    d1[u] = d2[u] = 0;
    for (auto &edge : adj[u])
    {
        int v = edge.to;
        if (v == p)
        {
            continue; // 避免回到父节点
        }
 
        DP(v,u); // 先递归子节点
 
        // 计算从 v 上来到 u 的距离
        long long dist = d1[v] + edge.weight;
 
        // 更新 u 的最长和次长路径
        if (dist > d1[u])
        {
            d2[u] = d1[u];
            d1[u] = dist;
        }
        else if (dist > d2[u])
        {
            d2[u] = dist;
        }
    }
    // 更新全局最长直径
    maxx = max(maxx,d1[u] + d2[u]);
}
 
int main()
{
    cin >> n;
    adj.resize(n + 1);
    for (int i = 0;i < n - 1;i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    DP(1,-1);
    cout << maxx * 10 + maxx * (maxx + 1) / 2 << endl;
}

枫禾(¬‿¬)

探索

P8602 大臣的旅费