EOJ Monthly 2021.3 Sponsored by TuSimple

QQ 小方给 QQ 小芳写了 $n$ 封情书，用 $n-1$ 条彩虹色的丝线串成了一棵树的样子。他想把这棵树叠成小小的一块，偷偷地塞进 QQ 小芳的背包里。

对于一棵无根树 $T=(V,E)$，结点 $i$ 有点权 $a_i$，无向边 $(u,v)$ 有边权 $w(u,v)$。

QQ 小方认为两个结点 $x,y$（$x\ne y$） 能够沿结点 $z$ 折叠，当且仅当

• $x,y$ 均与 $z$ 相邻，即 $(x,z)\in E, (y,z)\in E$。
• $a_x=a_y$ 且 $w(x,z) = w(y,z)$。

QQ 小方定义：结点 $x,y$（$x\ne y$）沿结点 $z$ 折叠的操作为：

• 将 $y$ 的所有除了 $(y,z)$ 以外的邻边 $(y,u)$（$u\ne z$）删除，并在 $T$ 中新増一条边 $(x,u)$。
• 删除结点 $y$ 和边 $(y,z)$。

容易发现，折叠完后的结构仍是一棵树。

QQ 小方希望找到一个最优方案，使得在执行若干次折叠操作后，树的结点数最小。

QQ 小方不想为难你，他只要求你输出最小的结点数。