2018年3月16日
点分治原理与实现
树分治系列:
概述
点分治是一种分治策略,其核心在于寻找树的重心,从重心分治解决,从而优化复杂度,实现O(\log n)的分治复杂度(不含分治中的处理复杂度)。
原理与实现
其实点分治的核心并不在于本篇文章介绍的内容,而是在于设计分治问题的思路上。因此本篇文章并没有多少内容。
找重心
分治的第一步是找到重心。树的重心指的是以该点为根的有根树的最大子树大小最小的点,这样的点满足其子树大小分布比较平衡,可以更好地缩小问题规模。在实际操作中,我们设计递归算法,将一个根的最大子树统计出来,注意其父亲的这一部分子树也要计入。
inline void getroot(int u, int fa) {
siz[u] = 1; msz[u] = 0;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to;
if(vis[v] || v == fa) continue;
getroot(v, u);
siz[u] += siz[v];
msz[u] = std::max(msz[u], siz[v]);
}
msz[u] = std::max(msz[u], sum - msz[u]);
if(msz[u] < msz[rt]) rt = u;
}
处理问题的流程
既然是分治,我们就要考虑分治的流程。
- 找到子树的重心,递归到子树重心去解决子问题
- 将子树的答案合并至当前树根
例题:【P3806】【模板】点分治1 – 洛谷
题目描述
给定一棵有n个点的树,询问树上距离为k的点对是否存在。
分析
这个k我们可以拆成树上从根出发的两条链计算。考虑点分治处理。
对于一个根,我们统计其所有儿子到根的距离。这些距离本身可以作为答案,而如果儿子不在同一个子树内,那么两个儿子到根的路径还可以拼成一条长链,也作为答案。
复杂度分析:找重心O(n),处理距离O(n),计算答案O(n^2)。可以表示为T(n)=kT(\frac{n}{k})+O(n^2),根据主定理,我们可以知道该算法的复杂度为O(n^2)。
诶说起来咋过的1e5啊,这个数据很玄学啊。
下面我们来讲O(n \log n)的写法,计算答案的拼接我们可以变成,找到一条路径,再二分查找是否存在加和为k的另外一条路径,这样做就可以O(n \log n)地统计答案,总复杂度也降下来了。然而我没写这种方法。
代码
// Code by KSkun, 2018/3
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 10005, INF = 1e9;
int n, m, ut, vt, wt, k, rt;
int siz[MAXN], dep[MAXN], has[10000005], msz[MAXN], sum;
bool vis[MAXN];
struct Edge {
int to, w;
};
std::vector<Edge> gra[MAXN];
struct Node {
int dis, subt;
} ans[MAXN];
int atot = 0;
inline void getroot(int u, int fa) {
siz[u] = 1; msz[u] = 0;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to;
if(vis[v] || v == fa) continue;
getroot(v, u);
siz[u] += siz[v];
msz[u] = std::max(msz[u], siz[v]);
}
msz[u] = std::max(msz[u], sum - siz[u]);
if(msz[u] < msz[rt]) rt = u;
}
inline void caldep(int u, int fa, int deep, int subt) {
ans[atot++] = Node {dep[u], subt};
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to, w = gra[u][i].w;
if(vis[v] || v == fa) continue;
dep[v] = dep[u] + w;
if(deep != 1) caldep(v, u, deep + 1, subt);
else caldep(v, u, deep + 1, v);
}
}
inline void work(int u) {
atot = 0;
dep[u] = 0;
caldep(u, 0, 1, -1);
for(int i = 0; i < atot; i++) {
for(int j = i + 1; j < atot; j++) {
if(ans[i].subt != ans[j].subt) {
has[ans[i].dis + ans[j].dis] = true;
}
has[ans[i].dis] = has[ans[j].dis] = true;
}
}
}
inline void dfs(int u) {
work(u);
vis[u] = true;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to;
if(vis[v]) continue;
rt = 0;
sum = siz[v];
getroot(v, 0);
dfs(rt);
}
}
int main() {
n = readint(); m = readint();
for(int i = 1; i < n; i++) {
ut = readint(); vt = readint(); wt = readint();
gra[ut].push_back(Edge {vt, wt});
gra[vt].push_back(Edge {ut, wt});
}
rt = 0;
msz[0] = INF;
sum = n;
getroot(1, 0);
dfs(rt);
while(m--) {
k = readint();
if(has[k]) puts("AYE"); else puts("NAY");
}
return 0;
}