DS 合集
Problem A. P5314 [Ynoi2011] ODT
题意：
给定一棵树，树有点权，要求支持路径加，查询一个点的距离小于等于 \(1\) 的邻域的 \(k\) 小点权。
\(1 \leq n, m \leq 10^6\)，\(3\) 秒，\(500\) MB。
解法：
小清新树剖题。
对于这类看似无从下手的树上问题，考虑树剖可能是一个很好的手段。
先将路径加改为到根路径加，树剖的很好性质是到根路径总会被分为 \(O(\log n)\) 条重链。于是一个自然的想法就出来了。对于每个点使用平衡树维护除了其重儿子和父亲外的点权。询问时重新插入即可。现在到根路径加只需要在轻重链改变时重构一下。同时要维护路径加单点求值，用树状数组维护即可。总复杂度 \(O(n \log^2 n)\)，可以通过。
Submission Link.
Problem B. P5311 [Ynoi2011] 成都七中
题意：
给你一棵 \(n\) 个节点的树，每个节点有一种颜色，有 \(m\) 次查询操作。
查询操作给定参数 \(l\ r\ x\)，需输出：
将树中编号在 \([l,r]\) 内的所有节点保留，\(x\) 所在连通块中颜色种类数。
每次查询操作独立。
\(1 \leq n, m, col \leq 10^5\)，\(l \leq x \leq r\)。时限 \(1\) 秒。
解法：
好题。
考虑 \(x\) 所在连通块的点，其充要条件为到 \(x\) 的路径上的点的最小值和最大值都在 \([l,r]\) 内。
这里有一个很显然的东西，设对 \(l,r,x\) 询问答案为 \(f(l,r,x)\)，我们发现对于任意一个和 \(x\) 连通的 \(y\)，都有 \(f(l,r,x)=f(l,r,y)\)，如果我们能方便的找到某个 \(y\)，且这个 \(y\) 的答案便于计算，那就好办了。
统计关于一个端点为 \(x\) 的路径时，一个套路是在点分树上考虑。发现我们如果找到最浅的 \(x\) 在点分树上的祖先 \(y\)，使得 \(y\) 与 \(x\) 是连通的，那么连通块其余点必然在点分树中 \(y\) 子树内。这个性质并不十分显然。如果存在某个 \(y\) 子树外的点和 \(x\) 连通，那么 \(x\) 必然和 \(x,y\) 在点分树上 LCA 连通，这个 LCA 必然在 \(y\) 之上，和 \(y\) 的最浅性不符。
对于每个询问找到 \(y\)，之后的事情就容易了。将询问挂到 \(y\) 上面，然后对于每个 \(y\)，对 \(y\) 子树内的点到 \(y\) 的路径的最小值和最大值统计答案，只需要简单的扫描线。总复杂度 \(O(n \log^2 n)\)，可以通过。
Submission Link.
Problem C. P7126 [Ynoi2008] rdCcot
题意：
给定一棵 \(n\) 个点的树，无边权。再给定一个常数 \(C\)，构造一个 \(n\) 个点的无向图，\((u,v)\) 连边当且仅当树上距离 \(dis(u,v) \leq C\)。
\(q\) 次询问，每次给定 \(l,r\)，求只保留图上 \([l,r]\) 内的点和边，图的连通块数量是多少。
解法：
很牛的一个题。
一个想法是，对连通块计数是困难的，但是如果能对于连通块对应成某个东西，对这个东西计数是容易的，题就做完了。
考虑对于每个连通块，找一个点代表整个连通块。这个点对于每个连通块是存在且唯一的。如果这样的点容易刻画性质，那么之后就好做了。
事实上，对于每个连通块，取 BFS 序最小的点作为代表元即可。对于非代表元点，可以说明连通块中必然存在一个点，BFS 序比其小且和其有直接连边。证明考虑每个非代表元，必然存在一条路径和代表元连通，如果这条路径长度为 \(1\) 则证毕，否则可以归纳证明。
于是问题转化为求区间中有多少点，满足不存在区间中的其余任何一个点满足 BFS 序小于他，且有直接连边。
考虑处理出 \(pre_i\) 和 \(nxt_i\) 表示编号 \(i\) 前最大的 BFS 小于 \(i\) 的 BFS 序，且距离符合条件的点。\(nxt\) 同理。求出后，即询问区间 \([l,r]\) 中有多少 \(i\) 满足 \(pre_i < l\) 且 \(nxt_i > r\)。这一部分直接数全局的，然后减去两边的，做三次离线扫描线即可。
如何求出 \(pre\) 和 \(nxt\) 呢？考虑点分治。很好的一点是这里的点分治不需要消除子树内的影响。于是对于每个分治重心将所有点拉出来按照 BFS 序做扫描线，线段树上二分即可。总复杂度 \(O(n \log^2 n + m\log n)\)。
Submission Link.
Problem D. P7124 [Ynoi2008] stcm
题意：
你要对于一棵树维护一个点集，支持插入和撤销。你需要在 \(O(n \log n)\) 的插入次数内维护出每个点的子树补集。即你需要对于每个点，存在某个时刻，集合是这个点子树补集。
具体来说，\(n \leq 10^5\)，你的插入次数不能超过 \(4.5 \times 10^6\)。
解法；
做法很多，但有一个十分厉害的分治做法。
考虑 DFS 序，每个点子树对应一个区间，那么子树补相当于前缀加后缀。
考虑直接在 DFS 序上分治，递归到 \([l,r]\) 内，满足已经加入 DFS 序在 \([1,l)\) 和 \((r,n]\) 中的点。对于包含于左右子区间的，插入后，递归处理，然后撤销。对于横跨中间的点，考虑扫描左端点从 \(l\) 到 \(mid\)，并将右端点移动维护所有要求区间。注意到 DFS 序的极强性质是任何两个子树区间要么不交要么包含，所以指针移动次数必然是对的。
这个做法拓展性很强。对于维护树上子集补的相关问题，大多都可以用这个做法维护。
Submission Link.