洛谷 P3304 [SDOI2013] 树的直径与LCA

[SDOI2013]直径

题目描述

小Q近期接触并掌握了部分图论相关知识。依据教材内容，存在以下定义。树：一种无回路且连通的无向图，其中每条边均被赋予正整数作为其长度的表示。若一棵树包含N个节点，则可以证明其边的数量严格等于N-1条。

路径：在树结构中，任意两个节点之间最多仅存在一条简单路径。我们以dis(a,b)来表示点a与点b之间路径上所有边长度的总和，并将该数值称为a与b两个节点之间的距离。

直径：在树结构中，最长路径被定义为树的直径。需要注意的是，该直径可能并非唯一。

目前小Q希望了解，在给定的一棵树中，其直径的具体长度是多少，并且有多少条边是所有可能的直径所必须经过的。

输入格式

输入的第一行给出一个整数N，用于表示图中的节点数量。随后的N-1行中，每一行包含三个整数a、b和c，表明节点a与节点b之间存在一条长度为c的无向边。

输出格式

输入内容包含两行数据。第一行给出一个整数，用于表示直径的长度。第二行则提供一个整数，用以描述所有直径所经过的边的数量。

样例分析与呈现

样例输入 #1

    6
    3  1 1000
    1  4 10
    4  2 100
    4  5 50
    4  6 100