774 . 樹直徑的逆襲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Josh
\begin{flalign} \LARGE\text{.} \end{flalign}

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

42.9% (3/7)

Tags

apcsc apcsc-graph

Description

本題改自 2020 TOI pB，原題要求嚴格次長樹直徑。

「你好阿小晨，真沒想到你可以解決樹直徑呢！
不過就到這裡為止了，接下來由我『非嚴格的次長樹直徑』來做為你的對手！」

沒錯，請你幫小晨找到這棵樹的非嚴格次長樹直徑。
更確切地說，請你先找到一條樹直徑，接者找到另外一條不同的路徑，使得這條新路徑的權重和越大越好。
請注意這條新路徑的權重和可能跟原先樹直徑一樣。

Input Format

第一行包含一個正整數 $N$ 代表節點數量。

接下來 $N-1$ 行每行有三個整數 $a, b, c$，代表 $a, b$ 之間有一條權重為 $c$ 的邊。

  • $3 \le N \le 2 \cdot 10^ 5$
  • $1 \le a, b \le N$
  • $a \neq b$
  • $0 \le c \le 10^ 9$
  • 保證整張圖連通

Output Format

輸出一個整數，代表這個非嚴格次長樹直徑的長度。

Sample Input 1

8
1 8 1
8 5 2
7 6 4
2 6 9
6 4 6
4 1 3
3 1 5

Sample Output 1

21

Hints

Problem Source

改自 2020 TOI pB

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~25 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
Submit
Back to Top