9 人解决,12 人已尝试。
10 份提交通过,共有 21 份提交。
5.8 EMB 奖励。
单点时限: 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$ 折叠,当且仅当
QQ 小方定义:结点 $x,y$($x\ne 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$),表示树边的两个端点和权值。
输出一个数表示最小结点数。
5 1 1 1 1 1 1 2 1 2 3 1 3 4 2 4 5 2
3
9 人解决,12 人已尝试。
10 份提交通过,共有 21 份提交。
5.8 EMB 奖励。