题解 P4178 【Tree】

### 这里要介绍一下不依靠容斥来避免点分治统计答案重复的方法 （下面简略介绍一下点分治算法的主要思想QwQ） 这个算法主要采用分治的思想：首先在树中选取一个节点作为树根，树根将这棵树分成了几个子树，我们统计这棵树树根对答案的贡献后，我们再用同样的方法递归处理树根的每一颗子树。为了使树分治出的子树尽量平均，尽可能最小化递归层数，我们每次选取当前树的重心作为根节点递归下去，保证递归层数在 $O(\log n)$ 级别。 本题要统计的是树上的路径，考虑树上路径分为经过根节点和不经过根节点两类。 故可以考虑在分治过程中，统计当前子树经过根节点的路径中，长度小于等于 $k$ 的路径即可。而对于那些不经过当前根节点的路径，我们将它们交给当前子树的子树处理。具体一点来说，可以考虑将经过根节点设其两段点为 $(x, y)$ 的路径拆分成两部分：$(root, x)$ 和 $(root,y)$，我们可以通过树形 dp 预处理出子树内每个点到根的距离 $dis[u]$，这样我们只需统计子树内点对 $x, y$ 满足 $dis[x] + dis[y] \leq k$ 的点对数量即可。 但这样有可能会统计到一些不符合要求的点对，即 $x, y$ 可能都在 $root$ 的同一棵子树中（如下图，$x, y$ 两点均在 $root$ 的黄色子树中），若此时也满足 $dis[x] + dis[y] \leq k$，则该点对也会被计入答案。而 $x,y$ 组成的路径显然没有经过根节点，故这条路径实际上是不合法的。我们需要考虑如何去掉这些不合法的路径。  现在正题开始！qwq 看到大家一般都使用的是容斥法处理的以上情况，即每次在统计当前子树根节点的答案后，再减去根节点的各个子节点的子树中满足条件的点对。这样可能会导致常数较大， 故这里介绍另外一种常数较小但细节相对较多的方法：**染色法**。 考虑我们在一次分治一个子树过程中，我们已经找到了其根节点 $root$，每个节点到根节点的距离 $dis[u]$，每个节点在 $root$ 哪一个**子节点**的子树中 $color[u]$（特别的，$color[root] = root$） 。 有一个显然的性质是，一条路径经过 $root$，当且仅当路径的两端点 $u, v$ 满足 $color[u] \neq color[v]$ 。 我们先将树中的节点都取出放至数组中，按照它们到根节点的距离（$dis[u]$）从小到大排序。排完序后，我们只需用两个指针 $i,j$，一个从前开始，一个从后开始扫描数组就可以计算出 $dis[x] + dis[y] \leq k$ 的点对 $(x,y)$ 的个数，其中 $x, y$ 分别是指针 $i,j$ 所指向的节点。 具体计算过程如下： 1、将左指针从左向右扫描，对每个点计算合法的路径条数。不难发现，在左指针扫描过程中，恰好使得 $(x, y)$ 满足 $dis[x] + dis[y] \leq k$ 的右指针位置是单调递减的。 2、对于如何去掉不合法的点对，我们可以维护一个数组 $f[i]$ 表示在左右两指针中间的点（包括左右两指针指向的点）中，满足 $color[u] = i$ 的点的个数。不难发现只有在左右指针移动时，$f$ 数组中的值才会发生变化，故 $f$ 数组可以在指针移动时直接维护。 3、设当前左指针指向的点为 $x$，则 $x$ 对答案的贡献为**左右指针中间的点的个数**减去**在这些点中与 $x$ 在 $root$ 相同子树中点的个数（即满足 $color[u] = color[x]$ 的点 $u$ 的个数）**，即 $j - i + 1 - f[color[x]]$ 。 显然上述排序时间复杂度为 $O(n \log n)$，扫描统计答案时间复杂度为 $O(n)$ 。 综上，结合 master 定理，本算法时间复杂度为 $O(n \log^2 n)$ 。 Code： ```cpp #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; namespace Primary { const int maxn = 40010; int n, m, dp[maxn], size[maxn], dis[maxn], help[maxn]; int head[maxn], to[maxn << 1], next[maxn << 1], val[maxn << 1], tot = 1; int root, sum, cnt, ans = 0, color[maxn], f[maxn]; bool vis[maxn]; bool cmp(int x, int y) {return dis[x] < dis[y];} inline void add_edge(int u, int v, int w) { to[++tot] = v; val[tot] = w; next[tot] = head[u]; head[u] = tot; } void getroot(int u, int pre)//树形 dp 求树的重心 { size[u] = 1, dp[u] = 0; for (int c = head[u], v; c; c = next[c]) { v = to[c]; if (v == pre || vis[v]) continue; getroot(v, u); size[u] += size[v]; dp[u] = max(dp[u], size[v]); } dp[u] = max(dp[u], sum - size[u]); if (dp[u] < dp[root]) root = u; } void getdis(int u, int pre)//对于当前子树预处理 dis, color, f 等数组 { help[++cnt] = u;//将当前子树节点编号均放入 help 数组中 color[u] = color[pre], ++f[color[u]]; for (int c = head[u], v; c; c = next[c]) { v = to[c]; if (v == pre || vis[v]) continue; dis[v] = dis[u] + val[c]; getdis(v, u); } } inline int calc(int u) { dis[u] = 0, cnt = 0; help[++cnt] = u; color[u] = u, f[color[u]] = 1;//注意预处理细节 for (int c = head[u], v; c; c = next[c]) { v = to[c]; if (vis[v]) continue; color[v] = v, dis[v] = val[c]; f[color[v]] = 0;//注意清空 f 数组 getdis(v, v); } sort(help + 1, help + cnt + 1, cmp);//将节点按 dis 从小到大排序 int i = 1, j = cnt, res = 0; while (i < j) { while (i < j && dis[help[i]] + dis[help[j]] <= m) { res += j - i + 1 - f[color[help[i]]]; --f[color[help[i]]];//指针移动时直接维护 f 数组,有些类似于莫队 ++i; } --f[color[help[j]]]; --j; } return res; } void solve(int u)//主要分治函数 { vis[u] = true; ans += calc(u); for (int c = head[u], v; c; c = next[c]) { v = to[c]; if (vis[v]) continue; sum = size[v] > size[u] ? n - size[u] : size[v];//计算下层递归子树大小 root = 0, dp[0] = n; getroot(v, u);//每次求出重心后继续分治 solve(root); } } void main() { scanf("%d", &n); for (int i = 1, u, v, w; i < n; ++i) { scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w), add_edge(v, u, w); } scanf("%d", &m); dp[0] = sum = n; getroot(1, 0); solve(root); printf("%d\n", ans); } } int main() { Primary::main(); return 0; } ```