4056. 我想把我的心意叠成小小的一块塞进你的心里

单点时限: 1.0 sec

内存限制: 256 MB

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 小方不想为难你,他只要求你输出最小的结点数。

输入格式

第一行一个整数 $n$($2\le n\le 10^5$),表示节点的数量。

接下来一行 $n$ 个正整数表示 $a_1,\ldots,a_n$($1\le a_i\le 10^9$)。

接下来 $n-1$ 行每行 $3$ 个数 $u_i,v_i,w_i$($1\le u_i,v_i\le n,1\le w_i\le 10^9$),表示树边的两个端点和权值。

输出格式

输出一个数表示最小结点数。

样例

Input
5
1 1 1 1 1
1 2 1
2 3 1
3 4 2
4 5 2
Output
3

9 人解决,12 人已尝试。

10 份提交通过,共有 21 份提交。

5.8 EMB 奖励。

创建: 3 年,11 月前.

修改: 3 年,8 月前.

最后提交: 1 年,4 月前.

来源: EOJ Monthly 2021.3

题目标签