传送门:https://www.luogu.com.cn/problem/P2664
看到有关两点间求贡献的题,首先想点分治
解决这道题,需要找到一个性质:
对于树上的一点i,若i的颜色是在该点到根这条链上第一次出现,那么他就可以对所有与它lca为根的点提供size[i]的贡献
画画图,发现性质非常正确,然后点分治处理下就可以了
2024-03-18 08:22:10
传送门:https://www.luogu.com.cn/problem/P2664
看到有关两点间求贡献的题,首先想点分治
解决这道题,需要找到一个性质:
对于树上的一点i,若i的颜色是在该点到根这条链上第一次出现,那么他就可以对所有与它lca为根的点提供size[i]的贡献
画画图,发现性质非常正确,然后点分治处理下就可以了