点分治小记

点分治是一类高效统计树上路径问题的算法，通过优化递归深度的方法来有效保证时间复杂度。

具体操作一般是以下几步：

• 找到当前子树的重心

• 以重心为根计算经过根节点的路径对答案的贡献

• 将根删去并递归处理它的所有子树

因为我们每次都以树的重心来作为根节点，递归深度不会超过 \(\log n\) 层。 每一层又顶多计算 \(n\) 个节点，因此时间复杂度为 \(O(n\log n)\)。

一般计算贡献有两种方式：

1.统计这棵树内所有路径贡献并将只在一棵子树内的减去。

2.直接枚举子树并计算贡献。

一般来说可以使用数据结构来辅助计算贡献，像线段树，树状数组以及单调队列都是不错的选择。

例题

P4178 Tree

第一种计算方式，配合一个双指针就可以了。

（主要是为了贴个代码）

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 1e5 + 10;
struct edge{
	int v, w, next;
}edges[N << 1];
int head[N], idx;
int n, k, siz[N], dis[N], root, rtsiz, ans;
int tmp[N], tp;
bool vis[N];

void add_edge(int u, int v, int w){
	edges[++idx] = {v, w, head[u]};
	head[u] = idx;
}

void getwson(int u, int fa, int nodeCnt){ 
	siz[u] = 1; int mxsz = 0;
	for(int i = head[u]; i; i = edges[i].next){
		int v = edges[i].v;
		if(v == fa || vis[v]) continue;
		getwson(v, u, nodeCnt); siz[u] += siz[v]; mxsz = max(mxsz, siz[v]);
	}
	mxsz = max(nodeCnt - siz[u], mxsz);
	if(mxsz < rtsiz) rtsiz = mxsz, root = u;
}

void getdis(int u, int fa, int d){
	tmp[++tp] = d;
	for(int i = head[u]; i; i = edges[i].next){
		int v = edges[i].v;
		if((!vis[v]) && v != fa) getdis(v, u, d + edges[i].w);
	}
}
void calc(int flag){
	sort(tmp + 1, tmp + tp + 1); int j = 0, ret = 0;
	for(int i = tp; i > 0; i--){
		while(tmp[i] + tmp[j + 1] <= k && j < tp) j++;
		ret += (j - (j >= i)); 
	}
	ans += (ret / 2) * flag; 
}

void solve(int u, int fa, int nodeCnt){
	rtsiz = nodeCnt - 1, root = u;
	tp = 0; getwson(u, fa, nodeCnt);
	vis[root] = true; getdis(root, 0, 0); calc(1);
	for(int i = head[root]; i; i = edges[i].next){
		int v = edges[i].v;
		if(v == fa || vis[v]) continue;
		tp = 0; getdis(v, root, edges[i].w); calc(-1);
	}
	for(int i = head[root]; i; i = edges[i].next){
		int v = edges[i].v;
		if(v == fa || vis[v]) continue;
		solve(v, root, siz[v]);
	}
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++){
		int x, y, w;
		cin >> x >> y >> w;
		add_edge(x, y, w); add_edge(y, x, w);
	}
	cin >> k;
	solve(1, 0, n);
	cout << ans;
	
	return 0;
}

2.P4149 [IOI2011] Race

第二种计算方法。

开一个桶 \(cnt\) 记录，路径权值为 \(w\) 时，路径边数的最小值。

然后对于一棵子树 \(v\) 到根的路径 \(i\) 权值 \(w\)，更新 \(ans = min(ans, dep[i] + cnt[k-w]])\)

注意计算的时候不要更新桶，一定要等到一棵子树的答案全部计算完之后再更新。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
struct edge{
	int v, w, next;
}edges[N << 1];
int head[N], idx;
int n, k, dep[N], siz[N], dis[N], root, rtsiz, ans = INF;
int tmp[N], tp, cnt[N];
bool vis[N];

void add_edge(int u, int v, int w){
	edges[++idx] = {v, w, head[u]};
	head[u] = idx;
}

void getroot(int u, int fa, int ncnt){
	siz[u] = 1; int mxsz = 0;
	for(int i = head[u]; i; i = edges[i].next){
		int v = edges[i].v;
		if(v == fa || vis[v]) continue;
		getroot(v, u, ncnt); siz[u] += siz[v]; mxsz = max(mxsz, siz[v]);
	}
	mxsz = max(mxsz, ncnt - siz[u]);
	if(mxsz < rtsiz) rtsiz = mxsz, root = u;
}

void getdis(int u, int fa, int d, int d2){
	tmp[++tp] = d; dep[tp] = d2; siz[u] = 1; 
	for(int i = head[u]; i; i = edges[i].next){
		int v = edges[i].v;
		if(v != fa && (!vis[v])) getdis(v, u, d + edges[i].w, d2 + 1), siz[u] += siz[v];
	}
}

void solve(int u, int fa, int ncnt){
	rtsiz = ncnt - 1, root = u;
	tp = 0; getroot(u, fa, ncnt);
	vis[root] = true; dep[root] = 0;
	for(int i = head[root]; i; i = edges[i].next){
		int v = edges[i].v;
		if(vis[v] || v == fa) continue; 
		getdis(v, root, edges[i].w, 1);
		for(int j = tp - siz[v] + 1; j <= tp; j++) if(tmp[j] <= k) ans = min(ans, dep[j] + cnt[k - tmp[j]]);
		for(int j = tp - siz[v] + 1; j <= tp; j++) if(tmp[j] <= k) cnt[tmp[j]] = min(cnt[tmp[j]], dep[j]);
	} 
	for(int i = 1; i <= tp; i++) if(tmp[i] <= k) cnt[tmp[i]] = INF;
	for(int i = head[root]; i; i = edges[i].next){
		int v = edges[i].v;
		if((!vis[v]) && u != fa) solve(v, root, siz[v]);
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0); 
	cin >> n >> k; memset(cnt, 0x3f, sizeof cnt); cnt[0] = 0;
	for(int i = 1; i < n; i++){
		int u, v, w; cin >> u >> v >> w;
		add_edge(v + 1, u + 1, w); add_edge(u + 1, v + 1, w);
	}
	solve(1, 0, n); 
	if(ans != INF) cout << ans;
	else cout << -1;
	
	return 0;
}

726f6a57-7dd3-4e25-8f40-391d8570e879