점분치란
트리 구조상의 경로 문제를 해결하기 위해 분치 tư duy를 적용하는 기법입니다. 경로를 두 부분으로 나눌 때, 하나는 중앙 노드를 지난 경로이고, 다른 하나는 중앙 노드를 지난 경로가 아닙니다.
중앙 노드를 지난 경로를 처리할 때는 분치 tư duy를 재귀적으로 하여 서브 트리로 문제를 전가합니다. 기본적으로 O(n²)의 복잡도를 가지지만, 각 단계에서 서브 트리의 중심점을 선택하면 복잡도를 O(n log n)으로 줄일 수 있습니다.
구현 방법
다음 함수들을 구현해야 합니다:
- solve: 분치 과정을 수행하는 함수
- get_center: 트리의 중심점을 찾는 함수
- calculate: 현재 노드를 지나는 경로의 기여를 계산하는 함수
예제
로우구 P3806 【템플릿】점분치 1
전송문 경로 길이를 기록하는 배열을 하나 만듭니다. 모든 질의를 먼저 읽은 후 경로에 도달하면 답변을 업데이트합니다. 전체 복잡도는 O(mn log n)입니다.
AC 코드
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <vector>
using namespace std;
const int maxn = 10010, bign = 10001000;
int n, m, tmp[bign], judge[bign];
int sz[maxn], vis[maxn];
int head[maxn], q[maxn];
int size, maxp[maxn];
int tot, rt, dis[maxn];
int qqq[maxn], ynn[maxn], cnt, p[maxn];
struct node {
int v, next, w;
} e[maxn * 2];
void insert(int u, int v, int w) {
cnt++;
e[cnt].v = v;
e[cnt].w = w;
e[cnt].next = p[u];
p[u] = cnt;
}
void get_center(int u, int fa) {
maxp[u] = 0;
sz[u] = 1;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v] || v == fa) continue;
get_center(v, u);
sz[u] += sz[v];
maxp[u] = max(maxp[u], sz[v]);
}
maxp[u] = max(maxp[u], tot - sz[u]);
if (maxp[u] < maxp[rt]) rt = u;
}
inline void get_distance(int u, int fa) {
tmp[++tmp[0]] = dis[u];
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v] || v == fa) continue;
dis[v] = dis[u] + e[i].w;
get_distance(v, u);
}
}
inline void calculate(int u) {
int ppp = 0;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
tmp[0] = 0;
dis[v] = e[i].w;
get_distance(v, u);
for (int j = 1; j <= tmp[0]; j++) {
for (int k = 1; k <= m; k++) {
if (q[k] >= tmp[j]) ynn[k] |= judge[q[k] - tmp[j]];
}
}
for (int j = 1; j <= tmp[0]; j++) {
if (tmp[j] >= bign) continue;
qqq[++ppp] = tmp[j];
judge[tmp[j]] = 1;
}
}
for (int i = 1; i <= ppp; i++) judge[qqq[i]] = 0;
}
inline void solve(int u) {
vis[u] = judge[0] = 1; calculate(u);
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
tot = sz[v];
maxp[rt = 0] = sz[v];
get_center(v, 0);
solve(rt);
}
}
int main() {
ios::sync_with_stdio(false);
memset(p, -1, sizeof(p));
cin >> n >> m;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
insert(u, v, w);
insert(v, u, w);
}
for (int i = 1; i <= m; i++) cin >> q[i];
maxp[rt = 0] = n;
tot = n;
get_center(1, 0);
solve(rt);
for (int i = 1; i <= m; i++) {
if (ynn[i]) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
CF161D 트리에서의 거리
전송문 기록되는 내용은 현재 길이 x의 경로 수입니다. 기타는 템플릿과 거의 같습니다.
AC 코드
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <vector>
using namespace std;
template<class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (f) x = -x;
}
template<class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
const int maxn = 50005;
long long ans;
int n, k, judge[maxn], tmp[maxn], siz[maxn], vis[maxn], p[maxn], cnt, tot, maxp[maxn], rt, dis[maxn], q[maxn];
struct node {
int v, next;
} e[maxn * 2];
void insert(int u, int v) {
cnt++;
e[cnt].v = v;
e[cnt].next = p[u];
p[u] = cnt;
}
void get_center(int u, int fa) {
maxp[u] = 0;
siz[u] = 1;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v] || v == fa) continue;
get_center(v, u);
siz[u] += siz[v];
maxp[u] = max(maxp[u], siz[v]);
}
maxp[u] = max(maxp[u], tot - siz[u]);
if (maxp[u] <= maxp[rt]) rt = u;
}
void get_distance(int u, int fa) {
tmp[++tmp[0]] = dis[u];
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (v == fa || vis[v]) continue;
dis[v] = dis[u] + 1;
get_distance(v, u);
}
}
void calculate(int u) {
int cntq = 0;
dis[u] = 0;
judge[0] = 1;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
tmp[0] = 0;
dis[v] = 1;
get_distance(v, u);
for (int j = 1; j <= tmp[0]; j++) if (k >= tmp[j]) ans += judge[k - tmp[j]];
for (int j = 1; j <= tmp[0]; j++) judge[tmp[j]]++, q[++cntq] = tmp[j];
}
for (int i = 1; i <= cntq; i++) judge[q[i]]--;
}
void solve(int u) {
vis[u] = 1; calculate(u);
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
maxp[rt = 0] = tot = siz[v];
get_center(v, -1);
solve(rt);
}
}
int main() {
memset(p, -1, sizeof(p));
read(n); read(k);
for (int i = 1; i < n; i++) {
int u, v;
read(u); read(v);
insert(u, v);
insert(v, u);
}
maxp[rt = 0] = tot = n;
get_center(1, -1);
solve(rt);
print(ans);
return 0;
}
로우구 P4149 [IOI2011]레이스
경로의 가중치를 기록하는 배열을 만듭니다. 가중치 합이 x인 경로의 가장 짧은 간선 수를 기록하는 배열을 만듭니다. 두 배열을 동시에 사용 및 초기화합니다.
AC 코드
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <vector>
using namespace std;
template<class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (f) x = -x;
}
template<class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
const int maxn = 2e5 + 5;
const int maxm = 1e6 + 5;
int n, k, judge[maxm], tmp[maxn], siz[maxn], vis[maxn], p[maxn], cnt, tot, maxp[maxn], rt, dis[maxn], q[maxn], dep[maxn], tmp2[maxn], anss[maxm], ans = 0x3f3f3f3f;
struct node {
int v, next, w;
} e[maxn * 2];
void insert(int u, int v, int w) {
cnt++;
e[cnt].v = v;
e[cnt].w = w;
e[cnt].next = p[u];
p[u] = cnt;
}
void get_center(int u, int fa) {
maxp[u] = 0;
siz[u] = 1;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v] || v == fa) continue;
get_center(v, u);
siz[u] += siz[v];
maxp[u] = max(maxp[u], siz[v]);
}
maxp[u] = max(maxp[u], tot - siz[u]);
if (maxp[u] <= maxp[rt]) rt = u;
}
void get_distance(int u, int fa) {
tmp[++tmp[0]] = dis[u]; tmp2[tmp[0]] = dep[u];
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (v == fa || vis[v]) continue;
dis[v] = dis[u] + e[i].w;
dep[v] = dep[u] + 1;
get_distance(v, u);
}
}
void calculate(int u) {
int cntq = 0;
dis[u] = 0;
anss[0] = 0;
judge[0] = 1;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
tmp[0] = 0;
dep[v] = 1;
dis[v] = e[i].w;
get_distance(v, u);
for (int j = 1; j <= tmp[0]; j++) if (k >= tmp[j] && judge[k - tmp[j]]) ans = min(ans, anss[k - tmp[j]] + tmp2[j]);
for (int j = 1; j <= tmp[0]; j++) {
if (tmp[j] > k) continue;
judge[tmp[j]] = 1;
anss[tmp[j]] = min(anss[tmp[j]], tmp2[j]);
q[++cntq] = tmp[j];
}
}
for (int i = 1; i <= cntq; i++) judge[q[i]] = 0, anss[q[i]] = 0x3f3f3f3f;
}
void solve(int u) {
vis[u] = 1; calculate(u);
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
maxp[rt = 0] = tot = siz[v];
get_center(v, -1);
solve(rt);
}
}
int main() {
memset(p, -1, sizeof(p));
memset(anss, 0x3f, sizeof(anss));
read(n); read(k);
for (int i = 1; i < n; i++) {
int u, v, w;
read(u); read(v); read(w);
u++; v++;
insert(u, v, w);
insert(v, u, w);
}
maxp[rt = 0] = tot = n;
get_center(1, -1);
solve(rt);
print(ans == 0x3f3f3f3f ? -1 : ans);
return 0;
}
로우구 P4178 트리
전송문 일시적인 방법은 상수항过大로 느리기 때문에, 트리状배열을 사용합니다. 경로 추가는 단점 수정이며, 답변 업데이트 시 접두어를 조회합니다. 답변을 업데이트하기 전에 경로 수를 저장하는 버킷을 초기화합니다.
AC 코드
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
template inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (f) x = -x;
}
template inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
const int maxn = 4e4 + 5;
const int maxx = 2e4 + 5;
int n, cnt, num, p[maxn], d[maxn], siz[maxn], maxp[maxn], tot, k, dis[maxn], tmp[maxn], ans, vis[maxn], rt;
struct node {
int v, next, w;
} e[maxn * 2];
void insert(int u, int v, int w) {
cnt++;
e[cnt].v = v;
e[cnt].w = w;
e[cnt].next = p[u];
p[u] = cnt;
}
inline int lowbit(int x) {
return x & -x;
}
void update(int x, int v) {
for (int i = x; i < maxx; i += lowbit(i)) d[i] += v;
}
int query(int x) {
int res = 0;
for (int i = x; i >= 1; i -= lowbit(i)) res += d[i];
return res;
}
void get_center(int u, int fa) {
siz[u] = 1;
maxp[u] = 0;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (v == fa || vis[v]) continue;
get_center(v, u);
siz[u] += siz[v];
maxp[u] = max(maxp[u], siz[v]);
}
maxp[u] = max(maxp[u], tot - siz[u]);
if (maxp[u] < maxp[rt]) rt = u;
}
void get_distance(int u, int fa) {
tmp[++tmp[0]] = dis[u];
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (v == fa || vis[v]) continue;
dis[v] = dis[u] + e[i].w;
get_distance(v, u);
}
}
void calculate(int u) {
int num = 0, q[maxn];
dis[u] = 0;
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
dis[v] = e[i].w;
tmp[0] = 0;
get_distance(v, u);
for (int j = 1; j <= tmp[0]; j++) {
if (k > tmp[j]) ans += query(k - tmp[j]);
if (k >= tmp[j]) ans++;
}
for (int j = 1; j <= tmp[0]; j++) {
if (k >= tmp[j]) {
q[++num] = tmp[j];
update(tmp[j], 1);
}
}
}
for (int i = 1; i <= num; i++) update(q[i], -1);
}
void solve(int u) {
vis[u] = 1;
calculate(u);
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (vis[v]) continue;
tot = maxp[rt = 0] = siz[v];
get_center(v, u);
solve(v);
}
}
int main() {
memset(p, -1, sizeof(p));
read(n);
for (int i = 1; i < n; i++) {
int u, v, w;
read(u); read(v); read(w);
insert(u, v, w);
insert(v, u, w);
}
read(k);
maxp[rt = 0] = tot = n;
get_center(1, -1);
solve(1);
print(ans);
return 0;
}