774 . 樹直徑的逆襲

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Josh
.

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

36.4% (4/11)

Tags

apcsc apcsc-graph

Description

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

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

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

Input Format

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

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

  • 3≤N≤2⋅105
  • 1≤a,b≤N
  • a≠b
  • 0≤c≤109
  • 保證整張圖連通

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