#P9097. 「HNOI2021 省集 Day4」我醉

    ID: 5181 传统题 6000ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理二分答案树算法点分治字符串双哈希子串哈希正反哈希判回文数据结构哈希表CF2600

「HNOI2021 省集 Day4」我醉

题目背景

猪王喝醉了,忘记了别人的名字。

题目描述

猪国的名字很有特点,它们都是一些回文串。

不仅如此,猪国的名字都来源于一棵 nn 个点的命名树。命名树的每条边上都写着一个猪国字符,可以用 [1,103][1, 10^3] 之间的整数表示。

猪国的名字都是命名树上某一条简单路径的边上所写字符所构成的字符串。

猪王今天喝醉了,他忘记了别人的名字。这时他想知道,对于一棵确定的命名树,名字最长可以有多长?

一句话题意:求树上最长回文串的长度,字符在边上,字符集为 [1,103][1, 10^3] 中的整数。

输入格式

从标准输入读入。

一行一个正整数 nn,表示命名树的大小。

接下来 n−1n − 1 行,每行三个正整数 x,y,zx, y, z,表示命名树上有一条 xx 连向 yy、写了字符 zz 的边。

输出格式

输出到标准输出。

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

样例

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

数据范围与提示

测试点编号 2≤n≤2\le n\le 特殊性质
1∼61\sim 6 100100 无
7∼107\sim 10 3×1033\times 10^3
11∼1211\sim 12 10510^5 命名树的形态是一条链。
13∼1413\sim 14 11 号点的度数为 n−1n-1。
15∼1615\sim 16 ii 号点的父亲在 [1,i−1][1,i-1] 中随机。
17∼2017\sim 20 无