点分治
序列上的操作可以用很多方式维护，线段树树状数组平衡树啥的，但是如果毒瘤出题人把序列搬到了树上，则需要一些奇妙方法。一般有两种（好几种？）方法：
- 树链剖分，把树上路径转化成 dfn 序上的多段进行操作。
- LCT，不多说，目前只会板子，没搞太懂。
- 点分治，这个是不用把树转化成序列的，而是将树上统计（一般为统计）进行一个分治。
- ......
接下来重点讲解第三种。
概述
在统计某类符合要求的路径数目时，可以将这种路径分为 2 类：
- 在根节点的各个儿子节点的子树内，不经过根节点。
- 经过当前选择的根节点。
对于第一种情况，我们可以直接把它分治到各个儿子节点的子树中，让它们自己去统计。
而对于第二种情况，我们可以把一条路径拆成两部分：到根节点和从根节点出发。这样每颗子树内部统计到根节点的路径，最后再合并即可。
时间复杂度分析
这块也是我这个蒟蒻刚刚稍微想明白了一点的
每次 dfs 一遍，差不多每经过一层会把整棵树遍历一遍，于是时间复杂度就取决于层数的多少。
当遇到数据构造成一条链时，时间复杂度可以卡到 \(O(n^2)\)，不能承受，因此我们需要尽可能减少树的层数，于是每次递归之前先找一下子树的重心，从重心再开始点分治，这样时间复杂度就能达到 \(O(n\log n)\)。
例题
P3806 【模板】点分治1
本题要统计树上是否存在距离为 \(k\) 的点对，我们可以把一条路径 \((u,v)\) 拆成 \((u, root)\) 和 \((root, v)\)，如果我们已经有了 \(dist_{u, root}\)，就可以在一个桶里查找是否存在一条路径 \((root, v)\) 使得 \(dist_{root, v} = k - dist_{u, root}\)。
同时向下递归之前要清空桶，这里不能直接 memset，会炸掉，于是用一个队列记录有多少点被改变过，最后只把这些点变为 0 即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, m, k;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
int siz[N], maxsiz[N];
int q[N];
bool tf[N * 10];
bool vis[N], res[N];
int rt;
inline void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
void calc_siz(int u, int fa, int sz)
{
siz[u] = 1;
maxsiz[u] = 0;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa || vis[j]) continue;
calc_siz(j, u, sz);
siz[u] += siz[j];
maxsiz[u] = max(maxsiz[u], siz[j]);
}
maxsiz[u] = max(maxsiz[u], sz - siz[u]);
if(maxsiz[u] < maxsiz[rt])
{
rt = u;
}
}
int dd[N], tt;
void calc_dist(int u, int fa)
{
dd[++ tt] = dist[u];
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa || vis[j]) continue;
dist[j] = dist[u] + w[i];
calc_dist(j, u);
}
}
queue<int> tag;
void dfz(int x, int fa)
{
tf[0] = true;
tag.push(0);
vis[x] = true;
for(int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa || vis[j]) continue;
dist[j] = w[i];
calc_dist(j, x);
for(int k = 1; k <= tt; k ++ )
for(int u = 1; u <= m; u ++ )
if(q[u] >= dd[k]) res[u] |= tf[q[u] - dd[k]];
for(int k = 1; k <= tt; k ++ )
if(dd[k] < 10000000)
{
tf[dd[k]] = true;
tag.push(dd[k]);
}
tt = 0;
}
while(!tag.empty()) tf[tag.front()] = false, tag.pop();
for(int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa || vis[j]) continue;
rt = 0;
maxsiz[rt] = INF;
calc_siz(j, x, siz[j]);
calc_siz(rt, -1, siz[j]);
dfz(rt, x);
}
}
int main()
{
memset(h, -1, sizeof h);
n = read(), m = read();
for(int i = 1; i < n; i ++ )
{
int a = read(), b = read(), c = read();
add(a, b, c), add(b, a, c);
}
for(int i = 1; i <= m; i ++ )
q[i] = read();
rt = 0;
maxsiz[rt] = INF;
siz[1] = n;
calc_siz(1, -1, n);
calc_siz(rt, -1, n);
dfz(rt, -1);
for(int i = 1; i <= m; i ++ )
if(res[i])
puts("AYE");
else puts("NAY");
return 0;
}
P4178 Tree
本题和上面差不多，只是多了查询点对的数量，因此用平衡树维护即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;
int maxsiz[N], siz[N], dist[N];
bool vis[N];
int rt;
int n, k;
struct fhq
{
struct node
{
int l, r;
int val, key;
int siz;
}t[N];
int root, cnt;
inline int New(int val)
{
t[++ cnt].val = val;
t[cnt].key = rand();
t[cnt].siz = 1;
t[cnt].l = t[cnt].r = 0;
return cnt;
}
inline void pushup(int p)
{
t[p].siz = t[t[p].l].siz + t[t[p].r].siz + 1;
}
int merge(int x, int y)
{
if(!x || !y) return x + y;
if(t[x].key > t[y].key)
{
t[x].r = merge(t[x].r, y);
pushup(x);
return x;
}
else
{
t[y].l = merge(x, t[y].l);
pushup(y);
return y;
}
}
void split(int p, int val, int &x, int &y)
{
if(!p) x = y = 0;
else
{
if(t[p].val <= val)
{
x = p;
split(t[p].r, val, t[x].r, y);
}
else
{
y = p;
split(t[p].l, val, x, t[y].l);
}
pushup(p);
}
}
int x, y, z;
inline void insert(int val)
{
split(root, val, x, y);
root = merge(merge(x, New(val)), y);
}
inline void clear()
{
cnt = root = 0;
}
inline int lowernums(int val)
{
split(root, val, x, y);
int res = t[x].siz;
root = merge(x, y);
return res;
}
} t;
inline void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void calc_siz(int u, int fa, int sz)
{
siz[u] = 1;
maxsiz[u] = 0;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa || vis[j]) continue;
calc_siz(j, u, sz);
siz[u] += siz[j];
maxsiz[u] = max(maxsiz[u], siz[j]);
}
maxsiz[u] = max(maxsiz[u], sz - siz[u]);
if(maxsiz[u] < maxsiz[rt])
{
rt = u;
}
}
int dd[N], tt;
void calc_dis(int x, int fa)
{
dd[++ tt] = dist[x];
for(int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa || vis[j]) continue;
dist[j] = dist[x] + w[i];
calc_dis(j, x);
}
}
ll ans;
void dfz(int u, int fa)
{
vis[u] = true;
t.insert(0);
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa || vis[j]) continue;
dist[j] = w[i];
calc_dis(j, u);
for(int i = 1; i <= tt; i ++ )
ans += t.lowernums(k - dd[i]);
for(int i = 1; i <= tt; i ++ )
t.insert(dd[i]);
tt = 0;
}
t.clear();
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa || vis[j]) continue;
rt = 0;
maxsiz[rt] = INF;
calc_siz(j, u, siz[j]);
calc_siz(rt, -1, siz[j]);
dfz(rt, u);
}
}
int main()
{
memset(h, -1, sizeof h);
n = read();
for(int i = 1; i < n; i ++ )
{
int a = read(), b = read(), c = read();
add(a, b, c), add(b, a, c);
}
k = read();
rt = 0;
maxsiz[rt] = INF;
calc_siz(1, -1, n);
calc_siz(rt, -1, n);
dfz(rt, -1);
cout << ans << endl;
return 0;
}
后记
其实点分治我还没有完全搞明白，现在做题也是大部分都是一头雾水，也因此只放了 2 道例题（能力有限），而且点分树什么的也没学，所以只能等以后再补充。
标签：cnt,dist,int,siz,分治,笔记,学习,maxsiz,root From： https://www.cnblogs.com/crimsonawa/p/17367844.html