zcmimi's blog

arrow_back树上差分共1篇文章

avatar
zc
2020-01-05 12:24:00
查看原题

点击跳转

考虑一种颜色对答案的贡献

把树中这种颜色的点都删掉,那么就会有很多的小树,这些小树中的点互相之间不会产生贡献,而不同树的两个点之间会产生贡献。

可以得到每一种颜色,点的sum值就是n - 所在小树的size

一个点的sum就是n * 颜色数 - 每种颜色节点所在小树的size

1/1
Search
search