牛客网 小睿睿的方案 解题报告

淀粉质,线段树,可持久化,扫描线

小睿睿虽然已经是人生赢家了，但当他看见学校里其他人秀恩爱时仍旧会十分不满。他的学校有\(n\)个教室，教室间有\(n-1\)条路径且任意教室互相联通，每天他和小熙熙会选择在两个不同的教室\((i,j)\)间的简单路径上秀恩爱。学校里一共有\(m\)对情侣，每对情侣中的两个人分别在教室\(A,B(A\not=B)\)，如果他们秀恩爱时经过的教室里存在任意一对情侣，这种秀恩爱的方案就是不合法的，求合法的无序点对数

无序点对：\((i,j)\)与\((j,i)\)视作同一对

第\(1\)行，\(2\)个整数\(n,m\)

第\(2\)至\(n\)行，每行两个整数\(a,b\)，表示\(a,b\)间存在一条边

之后\(m\)行，每行两个整数\(a,b\)，表示有一对情侣分别在教室\(a\)和教室\(b\)

一行一个整数，表示答案

对于\(30\%\)的数据，\(n,m\le 100\)

另有\(20\%\)的数据，\(n,m\le 100000\)且图的形态为一条链

对于\(100\%\)的数据，\(n,m\le 100000\)

输入数据较大，建议使用较快的读入方式

看了前两个题，发现很水，就来写这个题，然后最后5分钟的时候写出来了，结果数组还开小了，爆的只有80分...前面两个题还没做qaq

统计不合法的点对

首先搞一个点分。

然后考虑遍历一颗儿子的子树时，可能激活前面的儿子的一个子树，把这个激活放到线段树上就是区间覆盖，然后处理一个区间覆盖和区间查询1的个数，但是从点退回父亲的时候需要撤回，我没找到别的方法，只好硬肛了一个可持久化上去。

然后还有一个细节，就是当前子树点到分治中心的路径上有一对，这个可以激活之前的全部点，相应的，之前的子树也可能包含这样的链，就差不多处理就好了。

复杂度\(O(n\log^2 n)\)

\(O(n\log n)\)正解

这个题感觉好像是个套路，和接水果那题有点像

就是 处理树上路径包含统计数量之类的题目可以用\(dfs\)搞成二维的，然后贡献搞成矩形之类的，扫描线一下。

这个题可以对点对是祖孙关系和两个子树关系的东西讨论，然后弄成矩形覆盖的贡献，直接扫描线就可以了。

Code:(点分)

扫描线有机会补

2019.2.22