点分治

点分治常用于处理树上路径问题。

T1

例题

• 给定一棵有 $n$ 个点的树，$m$ 个询问树上距离为 $k$ 的点对是否存在。
  $1 \leq n\leq 10^4$，$1 \leq m\leq 100$，$1 \leq k \leq 10^7$。

题意转化为求长度为 $k$ 的路径是否存在。

从根节点入手，我们发现路径分为两类：
1.不经过根节点的路径
2.经过根节点的路径
对于第一类，我们分治到子树中计算，对于第二类，我们考虑如何计算。
首先遍历所有子树求出所有子孙到自己的距离，然后将不同子树中子孙到自己的路径两两进行拼接，直接开个 bool 数组进行统计即可，如子树中一点到自己的距离为 $v$ 则 $b_v = true$，并检查是否有 $b_{k - v} = true$，注意同一子树的路径不能拼接。

void getdist (int x, int fa) {
  t.push_back (dis); //记录路径
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) {
      dis[y] = dis + e[i].w;
      getdist (y, x);
    }
  }
} 

void dfs (int x, int fa) {
  vis = true;
  p[0] = true;//以x为端点的路径相当于 (son, x) 与 (x, x) 拼接
  _t.push_back (0); 
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) {
      dis[y] = e[i].w;
      getdist (y, x);
      for (int d : t) {
        for (int j = 1; j <= m; j++) //这里离线了询问
          if (q[j] >= d) res[j] |= p[q[j] - d]; //统计答案
      }
      for (int d : t) if (d <= 10000000 && !p[d]) p[d] = true, _t.push_back (d); 
      //更新bool数组（要当前子树统计完答案后更新，防止同子树路径合并）
      t.clear ();
    }
  }
  for (int x : _t) p = false;
  _t.clear ();
 ......
}

我们发现每到一个节点，都需要对其子树所有节点进行距离的计算，这样最劣情况下时间复杂度来到了 $O (n^2)$，因此我们希望每个子树的大小尽量均匀，于是我们在分治求解过程中，每一次求解一子树都选择从该子树的重心开始分治，于是我们在分治过程中寻找每个子树重心即可。

完整代码

#include <iostream>
#include <vector>
#define inf 2000000000
using namespace std;
const int maxn = 20010;
int n, m, cnt, sum, rt;
int h[maxn], siz[maxn], ms[maxn], dis[maxn];
bool p[10000010], res[maxn];
int q[maxn];
bool vis[maxn];
vector <int> t, _t;
struct E {
  int to, ne, w;
} e[maxn];
inline void add (int u, int v, int w) {
  e[++cnt].to = v; e[cnt].ne = h[u]; h[u] = cnt;
  e[cnt].w = w;
}
void find (int x, int fa) { //寻找重心并求出以该重心为根时子树的siz
  siz = 1; 
  ms = 0;
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) {
      find (y, x);
      siz += siz[y];
      ms = max (ms, siz[y]);
    }
  }
  ms = max (ms, sum - siz);
  if (ms <= ms[rt]) rt = x;
}
void getdist (int x, int fa) { //求距离
  t.push_back (dis);
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) {
      dis[y] = dis + e[i].w;
      getdist (y, x);
    }
  }
}
void dfs (int x, int fa) {
  vis = true;
  p[0] = true;
  _t.push_back (0);
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) {
      dis[y] = e[i].w;
      getdist (y, x);
      for (int d : t) {
        for (int j = 1; j <= m; j++) //这里做了离线
          if (q[j] >= d) res[j] |= p[q[j] - d];//统计答案，合并路径
      }
      for (int d : t) if (d <= 10000000 && !p[d]) p[d] = true, _t.push_back (d);
      t.clear ();
    }
  }
  for (int x : _t) p = false;
  _t.clear ();
  
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) { //分治
      rt = 0;
      ms[rt] = inf;
      sum = siz[y];
      find (y, x);
      find (rt, -1);
      //求子树重心
      dfs (rt, x);
    }
  }
}
int main () {
  cin.tie (0)->sync_with_stdio (false);
  cin >> n >> m;
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    add (u, v, w);
    add (v, u, w);
  }
  for (int i = 1; i <= m; i++) {
    cin >> q[i];
  }
  rt = 0;
  ms[rt] = inf;
  sum = n;
  find (1, 0);
  find (rt, -1);
  //寻找重心作为根节点
  dfs (rt, -1);
  //分治
  for (int i = 1; i <= m; i++) cout << (res[i] ? "AYE" : "NAY") << '\n';
  return 0;
}

T1

Luogu P4178
与上面没有大的区别，用树状数组维护信息即可。

#include <iostream>
#include <vector>
#define inf 1000000000
using namespace std;
const int maxn = 400010;
int n, k, rt, cnt, sum, ans;
int ms[maxn], siz[maxn], h[maxn];
int c[maxn], dis[maxn];
bool vis[maxn];
vector <int> t, _t;
struct E {
  int to, ne, w;
} e[maxn];
void M (int x, int v) {
  for (int i = x; i <= k; i += (i & -i)) c[i] += v;
}
int Q (int x) {
  int _ = 0;
  for (int i = x; i; i -= (i & -i)) _ += c[i];
  return _;
}
void add (int u, int v, int w) {
  e[++cnt].to = v; e[cnt].ne = h[u]; h[u] = cnt;
  e[cnt].w = w;
}
void find (int x, int fa) {
  ms = 0;
  siz = 1;
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) {
      find (y, x);
      siz += siz[y]; 
      ms = max (ms, siz[y]);
    }
  }
  ms = max (ms, sum - siz);
  if (ms <= ms[rt]) rt = x;
}
void getdist (int x, int fa) {
  t.push_back (dis);
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) {
      dis[y] = dis + e[i].w;
      getdist (y, x);
    }
  }
}
void dfs (int x, int fa) {
  vis = true;
  dis = 0;
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) {
      dis[y] = dis + e[i].w;
      getdist (y, x);
      for (int d : t) {
        if (d <= k) ans += Q (k - d) + 1;
      }
      for (int d : t) {
        if (d <= k) M (d, 1), _t.push_back (d);
      }
      t.clear ();
    }
  }
  for (int x : _t) M (x, -1);
  _t.clear ();
  for (int i = h; i; i = e[i].ne) {
    int y = e[i].to;
    if (y != fa && !vis[y]) {
      ms[rt = 0] = inf;
      sum = siz[y];
      find (y, x);
      find (rt, 0);
      dfs (rt, x);
    }
  }
}
int main () {
  ios::sync_with_stdio (false);
  cin.tie (0); 
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v, w; cin >> u >> v >> w;
    add (u, v, w); add (v, u, w);
  }
  cin >> k;
  sum = n;
  ms[rt = 0] = inf;
  find (1, 0);
  find (rt, 0);
  dfs (rt, 0);
  cout << ans;
  return 0;
}