懒得写代码了
1.http://oi.nks.edu.cn/zh/Problem/Details?cid=2719&tid=F
首先有个单次询问O（n）的换根DP做法。
像这种每次找一类点计算答案的题，考虑虚树。
有个结论：相遇点选在颜色为x或y的点上 不会更劣
所以只需要在同时包含x和y色的虚树上换根DP就行了
但复杂度波动不定。当max(size x,size y)比较大时，复杂度就高；
考虑均衡一下，根号分治。maxsize<sqrtn直接暴力，预处理所有maxsize>sqrtn的对，nsqrtn。（具体来说，对于每个size>sqrtn的点，在原树上换根DP。在颜色为k的点上时，就和k的虚树统计答案）
还有个小优化，每次建同时包含x色和y色的虚树时，不用按dfs重新排序，只需要把x色和y色的有序序列归并一下
O（nsqrtn+msqrtn）
标签：nsqrtn,复杂度,虚树,一些,思路,换根,DP,size From： https://www.cnblogs.com/zhuzc/p/18021757