题目描述

分治算法基础练习题 × 树算法基础练习题√

给一棵 $n$ 个节点的树，每一条边上有一个数字 $v \in [1,1000]$。

定义一个串 $(u,v)$ 为：将 $u$ 到 $v$ 的简单路径上每一个数字依次取出形成的数列。

一个长为 $n$ 的串 $A$ 是回文串，当且仅当 $\forall 1 \le i \le n,A_i=A_{n-i+1}$。

求树上的所有串中最长的回文串长度。

输入格式

第一行一个数 $n$ 表示树的大小。

此后 $n-1$ 行，每行三个数，表示边的两个端点和边权

输出格式

一行一个整数，表示可能的最长名字的长度。

样例数据

input1

5
1 2 3
2 3 3
2 4 2
2 5 3

output1

2

数据规模与约定

$2 \le n \le 100000$。