Codeforces 1213G Path Queries

cf题面

中文题面

给一棵无根树，每条边有边权。然后q个询问，每次询问给个w，求树上有多少对点之间的路径上的最大值小于等于w。

解题思路

离线。先把所有边按照边长升序排序，再把所有询问按照w升序排序。

之后从小到大处理每个询问。对于一个询问，首先由于询问已经排好序了，所以前一个答案是之前加的边对于答案的贡献，我们就先把上一个询问的答案直接复制过来，之后把小于等于这个询问的w的所有边加入到树上，然后并查集更新答案：每加一条边，对答案产生的贡献是“这条边两端的连通块”大小之积。

之后恢复顺序，输出，没了。

虚拟赛过程中看见这题的时候，想不到用并查集，而是想着深搜（类似CF1118 F1），对于一条边，讨论它下方的子树和上方树的其他部分的情况，但上方没想出来怎么处理，因为可能上方存在权值更大的边，不能一整个乘下去……然后想到点分治树分治啥的，全是xjb想……去看了这题的标签，dsu（并查集）、分治、排序。开始不知道啥是dsu，去百度找到了个dsu on tree，点进去发现时启发式合并，和这个没啥关系……

源代码

#include
#include
 
const int MAXN=2e5+5;
int n,m;
 
struct Que{
	int id,w;
	long long ans;
}q[MAXN];
bool cmp1(Que & a,Que & b){return a.w