niter的聖誕樹


Submit solution

Points: 100 (partial)
Time limit: 7.5s
Memory limit: 1G

Author:
Problem type

你現在有一棵 \(n(2\leq n\leq {10}^6)\) 個點的樹,每條邊可能會有不同的權重 \(w(1\leq w\leq {10}^9)\) ,

一開始每個點 \(v(1\leq v\leq n)\) 我們會塗上一個顏色 \(color(v) (1\leq color(v)\leq{10}^9)\) ,

我們定義 \(dis(i,j)\) 為「點 \(i\) 到點 \(j\) 所經過的唯一路徑的權重總和」 \((i\neq j)\) ,請輸出 \(\mathop{max}\limits_{1\leq i, j\leq n, color(i)=color(j)}{\{dis(i,j)\}}\) 的值。

Input

第一行只有一個數字 \(n\) 。 \((2\leq n\leq {10}^6)\)

第二行有 \(n\) 個數字 \(color(1), color(2), \dots, color(n)\) ,以空格間隔。 \((\forall 1\leq i\leq n, 1\leq color(i)\leq {10}^9)\)

第三行開始的 \(n-1\) 行,每行有三個數字 \(u, v, w\) (以空格間隔),代表點 \(u, v\) 之間有一條邊權為 \(w\) 的邊。 \((1\leq u, v\leq n, u\neq v, 1\leq w\leq {10}^9)\)

Output

請輸出 \(\mathop{max}\limits_{1\leq i, j\leq n, color(i)=color(j)}{\{dis(i,j)\}}\) 的值。

Constraints

第 \(1\) 組測資, \(n\leq 5000\) 。 \(~~(27\%)\)

第 \(2\) 組測資, \(n\leq 2\cdot {10}^5\) 。 \((60\%)\)

第 \(3\) 組測資,無特別限制。 \(~~(13\%)\)

Sample Input 1
7
1 1 2 2 3 2 3
3 4 2
4 2 28
2 1 22
1 6 7
4 5 18
6 7 13
Sample Output 1
88
Sample Input 2
3
1 3 2
2 3 2
2 1 8
Sample Output 2
0

Comments

There are no comments at the moment.