非常有趣的一道扫描线题,巧妙地把路径计数转化成求矩形面积并。
这题是找 LZW 学长要来的。
观察数据范围,有一个特殊的限制: > 同一颜色在树上出现不超过 20 次。
所以第一个想到的是可以枚举每种颜色,设该颜色的点数有 s 个,把一条路径不能包含两个同颜色的结点转化为两个同颜色的结点不能同时出现在一条路径上,用 O(s2) 找出这样的限制。
对于两个同颜色的点 u,v,分类讨论:
- 若 u,v 没有祖孙关系,则相当于所有路径两端分别在 u 的子树中和 v 的子树中的路径都不合法。
- 若 u 是 v 的祖先(可以交换),则设 u,v 路径上除 u 外距 u 最近的点为 t,则相当于所有路径两端,其一不在 t 的子树中,另一个在 v 的子树中,的路径都不合法。
这么多「子树」「子树」的,第一反应是用 DFS 序转化成一段区间,于是限制条件就变成了 n×n 矩阵上的子矩阵。
然后取一下矩阵的并,取补集,加上对角线再除以二就是答案了。
因为最后出来的对角线只有一条,直接除以二是不行的;根据题意显然对角线都是计入答案的,所以直接加上对角线(n 条路径)除以二即可。
注意扫描线本来是用于求矩形的并而我们求的是矩阵的并,需要做一些变化。
代码:
1 |
|