P3899 更为厉害

发表于 2024-09-19 分类于洛谷阅读次数： Waline：本文字数： 873 阅读时长 ≈ 3 分钟

考点

线段树合并

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 50;
int tot, head[maxn], ver[2 * maxn], nxt[2 * maxn];
// 每个点的深度d、子树大小（包含自己）sz、线段树根结点rt
int d[maxn], sz[maxn], rt[maxn];
// 线段树，下标是d，值是区间sz - 1之和
int cnt, lc[maxn * 50], rc[maxn * 50];
ll sum[maxn * 50];
int n;

void add(int x, int y) { ver[++tot] = y, nxt[tot] = head[x], head[x] = tot; }

void update(int &p, int l, int r, int x, int v) {
  if (!p) p = ++cnt;
  if (l == r) {
    sum[p] += v;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(lc[p], l, mid, x, v);
  else
    update(rc[p], mid + 1, r, x, v);
  sum[p] = sum[lc[p]] + sum[rc[p]];
}

// 新建节点方式合并
int merge(int p, int q, int l, int r) {
  if (!p || !q) return p + q;
  if (l == r) {
    sum[++cnt] = sum[p] + sum[q];
    return cnt;
  }
  int mid = l + r >> 1;
  int u = ++cnt;
  lc[u] = merge(lc[p], lc[q], l, mid);
  rc[u] = merge(rc[p], rc[q], mid + 1, r);
  sum[u] = sum[lc[u]] + sum[rc[u]];
  return u;
}

// 递归合并
void dfs(int x, int f) {
  d[x] = d[f] + 1;
  sz[x] = 1;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (y == f) continue;
    dfs(y, x);
    sz[x] += sz[y];
    rt[x] = merge(rt[x], rt[y], 1, n);
  }
  update(rt[x], 1, n, d[x], sz[x] - 1);
}

ll ask(int p, int l, int r, int L, int R) {
  if (L <= l && r <= R) return sum[p];
  ll ans = 0;
  int mid = (l + r) >> 1;
  if (L <= mid) ans += ask(lc[p], l, mid, L, R);
  if (R > mid) ans += ask(rc[p], mid + 1, r, L, R);
  return ans;
}

int main() {
  int q;
  scanf("%d%d", &n, &q);
  for (int i = 1, x, y; i < n; i++) {
    scanf("%d%d", &x, &y);
    add(x, y), add(y, x);
  }
  dfs(1, 0);
  for (int i = 1, a, k; i <= q; i++) {
    scanf("%d%d", &a, &k);
    ll ans = 1ll * min(k, d[a] - 1) * (sz[a] - 1) +
             ask(rt[a], 1, n, d[a] + 1, min(d[a] + k, n));
    printf("%lld\n", ans);
  }
}

思路

由于a和b都是c的祖先，显然a和b这两个点在同一条链上，

a和b的位置关系无非只有两种情况，假设根结点的深度从1开始，也就是d[1] = 1，

b在a上，根据乘法原理显然等于min(k, d[a] - 1) * (sz[a] - 1)

b在a下，显然满足以下公式： \[ \sum_{d\left[ a \right] +1\leqslant d\left[ b \right] \leqslant d\left[ a \right] +k}^{}{sz\left[ b \right] -1} \] 看见维护区间和，想到线段树；

但这道题是问每个节点满足上述式子的答案，那么对每个节点单独建立线段树即可，

父结点的线段树不仅仅可以记录自身，还可以通过线段树合并操作，将所有孩子的线段树信息一起并入自身。

d[x]作为线段树的下标，sz[x] - 1作为线段树叶子结点的值，操作为区间求和。

要注意！！！！本题不能使用合并思路的线段树合并写法，即不允许使用这个：

int merge(int p, int q, int l, int r) {
  if (!p || !q) return p + q;
  if (l == r) {
    ...
    return p;
  }
  int mid = (l + r) >> 1;
  lc[p] = merge(lc[p], lc[q], l, mid);
  rc[p] = merge(rc[p], rc[q], mid + 1, r);
  up(p);
  return p;
}