根号分治也是分治！

UnyieldingTrilobite · 2022-05-16 18:45:42 · 题解

lnk。

大家好啊这里是一个在线的 O(n^{1.5}) 的做法（假设 n,q,r 同阶）。

地区不好听，换个名字叫颜色好了。导师关系显然构成树形结构。

首先这种题一眼起手根分，把出现次数大于等于根号的颜色标记为“重颜色”，小于的标记为“轻颜色”。那么我们把询问 (u,v)（对应原题里的 (r1,r2)）分为三类处理。

注意到此时所有可能的询问一共 O(n^{1.5}) 种，可以预处理。我们可以对于每个点，把它子树内的“重颜色”分布贡献到它对应的颜色上去（这个分布可以按儿子向父亲转移，一遍 dfs 能搜完）。但这样的话我们注意到我们的空间需要开两个 O(n^{1.5}) 的数组。更优的做法是在 dfs 的时候维护一个“重颜色”分布的计数器，进入一个点的时候更新计数器（离开不更新），然后每个点子树内部的颜色分布就可以通过进入子树前和离开子树后的两波计数器作差求出。然后我们可以跳过先把贡献挂在每个点上再转给颜色这一步，可以直接给颜色更新贡献，不懂的可以看代码。

注意到此时所有可能的询问还是一共 O(n^{1.5}) 种，依旧可以预处理。注意到实际上有两种算贡献的方法：孩子把贡献给祖先，或者祖先从孩子处获得贡献。很显然，谁的颜色分布简单，就该由谁去主动操作贡献（不然很难精准定位贡献）。所以在第一种情况下是祖先从孩子处获取，那这回就是孩子把贡献给祖先了。我们同样维护一个“重颜色”分布的计数器，进入一个点的时候更新之，离开一个点的时候同样更新之。这样的话，我们遍历到一个点的时候，实际上计数器里存下的是它祖先们的“重颜色”分布。那我们把这个点的贡献给祖先，只需要枚举每一种“重颜色”然后根据它在祖先中的出现次数加贡献就好了。

这个时候我们发现两边都只有根号量级的点了。我们可以直接把这些点拉出来，然后观察如何给这个“子树内”另一个刻画。不难想到 dfs 序，那么我们设第一个序列是 a_1,a_2,\cdots,a_x，第二个是 b_1,b_2,\cdots,b_n，dfs 序列 为 dfn，一个点子树内的最大 dfs 序为 ed，那要统计的其实是这么一个东西：

我们发现那个双不等号很难处理，于是我们考虑把它拆开，然后柿子变成了：

我们发现前后两个柿子没啥形式上的区别而且都是一个类似于归并求逆序对（或者顺序对？）的形式，那显然是扫描线扫一扫就可以算的。而且我们甚至不需要为这个排序付出额外的代价——在 dfs 的过程中刻画这个序列的话，它应当天然是有序的（不过要看怎么刻画，也有可能天然倒序，反正就一个翻转序列的事）。

综上，我们这题就做完了。可能讲的有点意识流，放代码吧，没有精细实现，就图一个好写。跑挺慢的。不认识且结对出现且和带 nxt 的数组在一起的数组可以全部归为前向星（一共三个：存图，dfn，ed。基本上存法各有千秋，建议结合代码理解。注意前向星对边的编号没有要求，所以非常放飞自我，方便就完事了，希望不要有读者被误导。）

最后再说一个代码小细节吧，本来这题打算开 long long 的（因为虽然题目有那个保证但其实没查到的地方还是可能溢出，第三类情况依赖作差也很容易溢出），但考虑到不大美观，于是就使用了一个常用 trick：把 unsigned 当 long long 用，输出没问题且过程没 UB 就好了（

#include <bits/stdc++.h>
#define getchar()                                                              \
  (p1 == p2 && (p2 = (p1 = buf) + (cin.read(buf, 1 << 23).gcount()), p1 == p2) \
       ? EOF                                                                   \
       : *p1++)
using namespace std;
typedef unsigned ll;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 22], *O = obuf;
int rd() {
  char ch;
  while (!isdigit(ch = getchar()))
    ;
  int x = ch & 15;
  while (isdigit(ch = getchar())) x = x * 10 + (ch & 15);
  return x;
}
void prtln(ll x) {
  char s[15];
  int tot = 0;
  if (!x)
    *O++ = '0';
  else {
    while (x) s[++tot] = x % 10 | '0', x /= 10;
    while (tot) *O++ = s[tot--];
  }
  *O++ = '\n';
}
constexpr int N = 2e5 + 9, R = 2.5e4 + 9, Q = 2e5 + 9, B = 459;
int n, r, q;
int id[R], bel[N], ctot, cnt[R], tmp[B];
int hd[N], nxt[N], etot;
int dhd[R], dnxt[N];
int ehd[R], eto[N], enxt[N];
int tmpx[B], tmpy[B], totx, toty;
ll htl[B][R], occ[B], lth[R][B];
void dfs(int x) {
  int c = bel[x];
  dnxt[++etot] = dhd[c], dhd[c] = etot;
  for (int i = 1; i <= ctot; ++i) lth[c][i] -= occ[i];
  if (int i = id[c]) ++occ[i], ++tmp[i];
  for (int i = 1; i <= ctot; ++i) htl[i][c] += tmp[i];
  for (int y = hd[x]; y; y = nxt[y]) dfs(y);
  for (int i = 1; i <= ctot; ++i) lth[c][i] += occ[i];
  enxt[x] = ehd[c], ehd[c] = x, eto[x] = etot;
  if (int i = id[c]) --tmp[i];
}
ll calcxy() {
  ll ans = 0;
  for (int i = 0, j = 0; j < toty; ++j) {
    while (i < totx && tmpx[i] <= tmpy[j]) ++i;
    ans += i;
  }
  return ans;
}
ll calcans(int u, int v) {
  if (id[v])
    return lth[u][id[v]];
  else if (id[u])
    return htl[id[u]][v];
  totx = 0, toty = 0;
  for (int i = dhd[v]; i; i = dnxt[i]) tmpx[totx++] = i;
  reverse(tmpx, tmpx + totx);
  for (int i = ehd[u]; i; i = enxt[i]) tmpy[toty++] = eto[i];
  reverse(tmpy, tmpy + toty);
  ll ans = calcxy();
  toty = 0;
  for (int i = dhd[u]; i; i = dnxt[i]) tmpy[toty++] = i - 1;
  reverse(tmpy, tmpy + toty);
  return ans - calcxy();
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  n = rd(), r = rd(), q = rd();
  ++cnt[bel[1] = rd()];
  for (int i = 2, s; i <= n; ++i) {
    nxt[i] = hd[s = rd()], hd[s] = i;
    ++cnt[bel[i] = rd()];
  }
  for (int i = 1; i <= r; ++i)
    if (cnt[i] >= B) id[i] = ++ctot;
  dfs(1);
  while (q--) {
    int u = rd(), v = rd();
    prtln(calcans(u, v));
  }
  return cout.write(obuf, O - obuf).flush(), 0;
}