P2664 树上游戏

传送门:https://www.luogu.com.cn/problem/P2664

看到有关两点间求贡献的题,首先想点分治

解决这道题,需要找到一个性质:

对于树上的一点i,若i的颜色是在该点到根这条链上第一次出现,那么他就可以对所有与它lca为根的点提供size[i]的贡献

画画图,发现性质非常正确,然后点分治处理下就可以了

上一篇:​​ ​​Java后端学习路线图,你真的只需要这一张!


下一篇:P2664 树上游戏