天边的生活の博客

树分治

是序列分治的一种拓展。

使用场景

求经过某些点满足某种条件的路径数量。

引入

给定长度为 $n$ 的序列 $a$。求是否存在一对 $(x,y)(1\le x<y\le n)$ 满足 $\sum\limits^y_{i=x}a_i$ 恰好为 $k$。

数据范围：$1\le n\le 10^5,|a_i|\le 10^4$。

将前述问题搬到树上，就变成了 P3806 【模板】点分治 1

因此，点分治的思想为：对于每一棵根节点为 $x$ 的子树，讨论经过 $x$ 和不经过 $x$ 的情况。

为了确保时间复杂度，每次寻找子树的重心作为当前的根节点（如果树是一条链，那么时间复杂度至少为 $O(n^2)$），使得递归次数上限为 $\log n$。

不过上面那道题太神奇了，所以我们用这一题做例题：CF1923E Count Paths。

实例代码：

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 5e4 + 5;
int n, k, sz[MAXN], p, len[MAXN], tmp[MAXN], ans, cnt;
bool vis[MAXN];
vector<int> a[MAXN];
void dfs1(int x, int fa){
  sz[x] = 1;
  int maxx = 0;
  for (auto v : a[x]){
    if (!vis[v] && v != fa){
      dfs1(v, x);
      if (p != -1){
        return ;
      }
      sz[x] += sz[v];
      maxx = max(maxx, sz[v]);
    }
  }
  maxx = max(maxx, n - sz[x]);
  if (maxx <= n / 2){
    p = x;
    sz[fa] = n - sz[x];
  }
}
void dfs3(int x, int fa, int l){
  if (l > k){
    return ;
  }
  tmp[++cnt] = l;
  ans += len[k - l] + (l == k);
  for (auto v : a[x]){
    if (!vis[v] && v != fa){
      dfs3(v, x, l + 1);
    }
  }
}
void dfs2(int x){
  for (auto v : a[x]){
    if (!vis[v]){
      dfs3(v, x, 1);
      for (int i = 1; i <= cnt; i++){
        len[tmp[i]]++;
      }
      cnt = 0;
    }
  }
  for (int i = 1; i <= n; i++){
    len[i] = 0;
  }
  vis[x] = 1;
  for (auto v : a[x]){
    if (!vis[v]){
      n = sz[v];
      p = -1;
      dfs1(v, 0);
      dfs2(p);
    }
  }
}
signed main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for (int i = 1, u, v; i < n; i++){
    cin >> u >> v;
    a[u].push_back(v);
    a[v].push_back(u);
  }
  p = -1;
  dfs1(1, 0);
  dfs2(p);
  cout << ans;
  return 0;
}