最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • As far as possible

    正文概述 陈老师   2026-01-20 15:15:16  

    题目描述

    给定一棵包含 NN 个顶点的树。顶点编号为 1,2,…,N1, 2, \ldots, N。
    第 ii 条边(1≤i≤N−11\leq i\leq N-1)连接顶点 UiU_i 和顶点 ViV_i,长度为 LiL_i。

    对于 K=1,2,…,NK=1,2,\ldots,N,请解决以下问题。

    高桥君和青木君进行一个游戏。游戏规则如下:

    • 首先,青木君在树上指定 KK 个互不相同的顶点。
    • 然后,高桥君需要构造一条起点和终点均为顶点 11 的“步道”,并且该步道必须经过青木君指定的所有顶点。

    高桥君构造的步道的长度定义为分数。高桥君希望分数尽可能小,青木君希望分数尽可能大。请你求出当两人都采取最优策略时的分数。

    步道的定义:在无向图(包括树)上,步道是指由 kk 个顶点(kk 为正整数)和 k−1k-1 条边交替组成的序列 v1,e1,v2,…,vk−1,ek−1,vkv_1,e_1,v_2,\ldots,v_{k-1},e_{k-1},v_k,其中每条边 eie_i 连接顶点 viv_i 和 vi+1v_{i+1}。序列中同一个顶点或同一条边可以出现多次。步道经过顶点 xx,是指存在 1≤i≤k1\leq i\leq k 使得 vi=xv_i=x(可以有多个这样的 ii)。步道的起点和终点分别为 v1v_1 和 vkv_k,步道的长度为 e1,e2,…,ek−1e_1,e_2,\ldots,e_{k-1} 的长度之和。

    输入格式

    输入以以下格式从标准输入读入。

    NN
    U1U_1 V1V_1 L1L_1
    U2U_2 V2V_2 L2L_2
    ⋮\vdots
    UN−1U_{N-1} VN−1V_{N-1} LN−1L_{N-1}

    输出格式

    输出 NN 行。第 ii 行(1≤i≤N1\leq i\leq N)输出 K=iK=i 时问题的答案。

    样例

    5
    1 2 3
    2 3 5
    2 4 2
    1 5 3
    
    16
    22
    26
    26
    26
    
    3
    1 2 1000000000
    2 3 1000000000
    
    4000000000
    4000000000
    4000000000
    

    提示

    样例解释

    样例1 当 K=1K=1 时,青木君最优地指定顶点 33,此时高桥君可以构造步道 1→2→3→2→11\to 2\to 3\to 2\to 1,最优分数为 1616。当 K=2K=2 时,青木君最优地指定顶点 3,53,5,此时高桥君可以构造步道 1→5→1→2→3→2→11\to 5\to 1\to 2\to 3\to 2\to 1 等,最优分数为 2222。当 K≥3K\geq 3 时,双方最优时分数为 2626。

    样例2 注意答案可能超出 3232 位整数范围。

    数据范围

    • 2≤N≤2×1052\leq N\leq 2\times 10^5
    • 1≤Ui<Vi≤N1\leq U_i < V_i\leq N
    • 1≤Li≤1091\leq L_i\leq 10^9
    • 输入均为整数
    • 给定的图为一棵树。
    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » As far as possible