题面 传送门：洛谷 Solution 首先，长成这样的题目一定是淀粉质跑不掉了。 考虑到我们不知道K的大小，我们可以开一个splay来统计比某个数小的数的数量。 不会点分治的戳我 Code #include<iostream> #include<vector> #include<cstdio> using namespace std; long long read() { long long x=0,f=1; char c=getchar(); while(!isdigit(c)…

什么是淀粉质点分治？ 就是把分治搬到树上，以某个点为根，分别分治处理子树的答案，再计算子树与子树间的答案的玄学算法。 举个例子： 如何求出一颗树上距离为K且所经过的点最少的点对？ 对于这种题，我们可以把某个点（一般为重心）作为根，然后对左右子树递归处理，先分别得出左右子树的答案，再求出横跨两个子树之间的点对的答案。 为什么要学淀粉质 对于上面那道题，如果我们用传统的暴力做法，最优的复杂度只能得到O(n2)的暴力枚举，但是如果我们用淀粉质来搞，我们就可以做到O(n∗logn)的复杂度（如果K很大的话，我们可能还得套个…