점분치 점분나무 학습 잉여문

0. 서론

---

이蒟蒻는 이 점분나무 템플릿을 3일 동안 보고서야 이해할 수 있었다

매우 화나웠다

그래서 이 점분치와 점분나무 학습 내용을 정리한 잉여문을 작성해두기로 했다 이 잉여문은 매우 임의적입니다, 흥미로운 마음으로 보시면 됩니다

1. 점분치

---

1.1. 도입

문제: 트리 상에서 특정 조건을 만족하는 경로 수를 구하는 방법은 무엇인가?

예를 들어: 트리 상에서 u에서 v로의 최단 경로 길이가 k 이하인 (u, v)의 수를 구하라

显然, 우리가 직접 폭력적인 방법을 사용하면 복잡도가 \(O(n^3)\)로 급증하여 TLE가 발생할 것이다

따라서 주의를 집중하여 복잡도를 낮추는 방법을 강구해야 한다

(u, v)에 대해, 우리는 각 점에서 발생하는 기여를 미리 처리한 후 합산하는 방식을 사용할 수 있다

그러면 어떻게 처리할 수 있을까?

1.2. 방법론

1.2.1. 문제 전환

루트 점 u에 대해, u의 서브트리에서 경로를两类로 분류할 수 있다:

1. u를 지난 경로
2. u를不经한 경로

이렇게 분류有何ประโยชน가 있을까?

众所周知, DFS를 통해 트리 상의 모든 점을 방문할 수 있다

그러면, type 2의 경로를 DFS를 진행하며 type 1로 전환할 수 있다

그러면 type 1은 어떻게 처리할까?

트리를 그려서 관찰해보자 (블로그园에서 이미지 크기가 작아져 있습니다, 새 탭에서 열어보세요)

u를 지난 경로의 길이

\(dis(x,y) = dis(x,u) + dis(y,u)\)

예를 들어, 그림 중에서 u를 지난 합법적인 경로는 다음과 같습니다:

s1 -> u -> s2 (4 + 7 = 11), s1 -> u -> s3 (4 + 6 = 10)

s1 -> u (4 + 0 = 4), s2 -> u (7 + 0 = 7), s3 -> u (6 + 0 = 6)

(u로 직접 가는 것도 합법입니다)

그러면, 우리가 해결해야 할 문제는 다음과 같습니다: (x, y)에 대해 \(dis(x,u) + dis(y,u) ≤ k\)고 \(b[x] ≠ b[y]\)인 쌍의 수를 구하는 것이다

d[i] = dis(i, u) → i에서 루트 u까지의 거리

b[i] = i가 u의 어느 서브트리(s1, s2, s3,...)에 속하는지

왜 \(b[x] ≠ b[y]\) 조건이 필요할까?

트리를 보면 만약 이 조건을 없애면 x -> u -> x, x -> u -> fa[x], x -> u -> s1와 같은 경로가 모두 u가 발생시키는 합법적인 경로로 포함될 것이다

그러나 이 경로들은 최단 경로가 아니므로 제외해야 한다

1.2.2. 답변 통계 최적화

그러면 질문이 나옵니다: 방송국 방송국,여기서 d[i]를 나열하더라도 여전히 \(O(n^2)\)가 아닌가?

걱정하지 마세요, 우리는 문제를 매우 세련된 형태로 전환했어요

다음과 같이 \(dis(x,u) + dis(y,u) ≤ k\)를 관찰하면:

d[x] + d[y] ≤ k

이제 이것을 정렬된 배열에서 관찰하면, 이중 포인터 기법을 사용할 수 있습니다

모든 점을 d[i]로 정렬한 후, 이중 포인터 [L, R]를 사용하여:

• d[L] + d[R] ≤ k → L이 R와 L+1에서 R까지와의 모든 짝을 기여
• ans += R - L
• L을 증가시키고 R을 조정하여 조건을 유지

그러나 같은 서브트리 내의 짝은 제외해야 한다

이를 위해, b[L]에 해당하는 서브트리의 점수를 유지하며 cnt[b[L]]로 관리한다

즉, \(ans += R - L - cnt[b[L]]\)로 처리한다

이 방법으로 \(O(n)\)의 복잡도를 제거하고, 각 서브트리의 처리 복잡도를 \(O(n + log n)\)로 줄인다

1.2.3. 중심

점분치의 또 다른 중요한 작업은 중점을 찾는 것이다

1.2.3.1. 정의

중점이란 무엇인가?

물리학에서의 중점과 유사한 개념이다

(참고: <당장은 이 부분은 생략하고, OI에서의 정의를 따른다>)

OI에서 트리의 중점은 자식 서브트리 중 가장 큰 크기의 서브트리를 최소화하는 점이다

1.2.3.2. 사용 이유

왜 중점을 사용하는가?

현재의 복잡도는 각 점을 처리하는 데 \(O(n)\)씩 소요된다

코드가 TLE를 피하기 위해 총 복잡도를 \(O(n^2)\) 이하로 유지해야 한다

중심을 통해 분치를 수행하면, 각 분치 단계에서 서브트리 크기가 절반 이하로 줄어들어, \(O(log n)\)의 분치 깊이를 실현할 수 있다

트리를 그려서 이해하자:

114514+3개의 점을 가진 트리에서, 루트를 U로 설정하고 하향식 DFS를 수행하면, S1 서브트리가 1개의 점, S2 서브트리가 114514+1개의 점을 가질 수 있다

S2 서브트리를 처리할 때와 S1을 처리할 때의 복잡도가 유사하다

이와 같이, 각 분치 단계에서 서브트리 크기가 절반 이하로 줄어들지 않으면, 복잡도가 \(O(n^2)\)로 퇴화한다

따라서, 각 분치 단계에서 서브트리 크기 중 가장 큰 값을 가지는 점을 중점으로 설정하고, 중점을 통해 분치를 수행한다

이 작업은 DFS 중에 미리 예리하게 처리할 수 있다

1.3. 템플릿 코드

마지막으로 흥미로운 템플릿 코드를 첨부합니다:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 40005;
const int INF = 0x3f3f3f3f;
int n, k;
int aa, bb, cc;
struct Node {
    int v, w;
};
vector<Node> children[N];
void add(int a, int b, int c) {
    children[a].push_back({b, c});
    children[b].push_back({a, c});
}
int depth[N]; // 깊이
int dist[N]; // 루트까지의 거리
int visited[N]; // 분치 여부
Node distances[N]; // 거리 정보 저장
int count;
int root;
int max_size[N]; // 서브트리 중 최대 크기
int size[N]; // 서브트리 크기
int answer; // 최종 답변 
int current_size; // 현재 서브트리 크기 
int cnts[N]; // 통계용 카운트
int b_subtree[N]; // 서브트리 ID
int queue_arr[N];
int pointer = 0;
bool compare(Node x, Node y) {
    return x.w < y.w;
}
void find_center(int u, int fa) { // 중점 찾기 
    size[u] = 1;
    max_size[u] = 0;
    for (auto to : children[u]) {
        int v = to.v;
        int w = to.w;
        if (v == fa || visited[v]) continue;
        find_center(v, u);
        size[u] += size[v];
        max_size[u] = max(max_size[u], size[v]);
    }
    max_size[u] = max(max_size[u], current_size - max_size[u]);
    if (max_size[u] < max_size[root]) {
        root = u;
    }
}
void get_depth(int u, int fa) { // 깊이와 거리 계산 
    distances[++count] = {u, dist[u]};
    if (depth[u] > 1) {
        b_subtree[u] = b_subtree[fa];
    } else if (depth[u] == 1) {
        b_subtree[u] = u;
    }
    for (auto to : children[u]) {
        int v = to.v;
        int w = to.w;
        if (visited[v] || v == fa) continue;
        dist[v] = dist[u] + w;
        depth[v] = depth[u] + 1;
        get_depth(v, u);
    }
    return;
}
int calculate_answer(int u) { // 중점에서의 답변 계산 
    dist[u] = depth[u] = current_size = 0;
    pointer = 0;
    count = 0;
    b_subtree[u] = 0;
    get_depth(u, 0);
    sort(distances + 1, distances + count + 1, compare);
    memset(cnts, 0, sizeof(cnts));
    int left = 1, right = count, ans = 0;
    for (int i = 2; i <= count; i++) {
        cnts[b_subtree[distances[i].v]]++;
    }
    while (left < right) {
        if (distances[left].w + distances[right].w <= k) {
            ans += right - left - cnts[b_subtree[distances[left].v]];
            left++;
            cnts[b_subtree[distances[left].v]]--;
        } else {
            cnts[b_subtree[distances[right].v]]--;
            right--;
        }
    }
    return ans;
}
void divide(int u) { // 분치 
    visited[u] = 1;
    b_subtree[u] = u;
    answer += calculate_answer(u);
    memset(depth, 0, sizeof(depth));
    memset(dist, 0, sizeof(dist));
    for (auto to : children[u]) {
        int v = to.v;
        int w = to.w;
        if (visited[v]) continue;
        current_size = size[v];
        max_size[root = 0] = INF;
        find_center(v, 0);        
        divide(root);
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> aa >> bb >> cc;
        add(aa, bb, cc);
    }
    cin >> k;
    current_size = n;
    max_size[root = 0] = INF;
    find_center(1, 0);
    find_center(root, 0);
    divide(root);
    cout << answer << endl;
}

<완료! 🎉>

2. 점분나무

---

2.1. 도입

점분치 기반에 조회와 수정 작업을 추가하면 어떻게 될까?

이 경우, 복잡도가 \(O(n^2 log n)\)로 급증하여 TLE가 발생한다

2.2. 방법론

복잡도를 줄이는 방법은 무엇인가?

우리가 최적화할 수 있는 부분은 무엇인가?

• \(n\): 중점을 찾는 단계
• \(log n\): 분치 깊이
• \(n\): 이중 포인터를 사용하여 답변을 계산하는 단계

복잡도가 가장 많이 발생하는 부분을 집중 분석한다

중점을 찾는 단계에서, 중점의 분포는 트리의 구조에 따라 결정된다

점의 가중치가 변경되더라도, 중점의 분포는 영향을 받지 않는다

왜냐하면 중점은 트리의 구조에만 의존하기 때문이다

따라서, 중점을 미리 예리하게 계산하고, 이에 기반하여 트리를 재구축할 수 있다

이른바, '점분나무'라는 이름의 새로운 트리를 형성한다

2.3. 답변 계산

2.3.1. 思考

점분나무를 통해 답변을 구하는 방법은 무엇인가?

• 트리의 구조와 점의 가중치를 활용한다
• 각 중점에서의 기여를 계산하고, 이를 누적한다

2.3.2. 구현

• 각 중점 u에 대해, T[0][u][s]는 u를 지나는 경로 중 거리가 s인 점의 가중치 합을 저장한다
• T[1][u][s]는 u의 서브트리 내에서 같은 서브트리에 속하는 점의 거리가 s인 경로의 가중치 합을 저장한다

조회 시, T[0][u]에서 값을 조회한 후, T[1][u]를 통해 중복된 값을 제외한다

2.4. 코드

코드를 통해 구체적인 구현 방법을 보자

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

const int N = 1e5 + 5;
const int MAXN = 35;
const int INF = 0x3f3f3f3f3f;

int n, m;
int B[N]; // 원 트리의 가중치
int A[N]; // 현재 가중치 
vector<int> children[N]; // 원 트리의 인접 리스트 
int root;
int depth[N]; // u의 조상 중점层数 
int visited[N]; // 분치 여부 
int fa[N][MAXN]; // fa[u][i] → u의 i번째 조상 중점 
int dists[N][MAXN]; // dists[u][i] → u에서 fa[u][i]까지의 거리 
int max_size[N]; // 서브트리 중 최대 크기
int size_subtree[N]; // 서브트리 크기 
vector<int> T[2][N]; // T[0/1][u] → 중점 u에서의 거리 배열

void ADD(int x, int y) {
    children[x].push_back(y);
    children[y].push_back(x);
    return;
}

void find_center(int u, int f, int sum) {
    max_size[u] = 0;
    size_subtree[u] = 1;
    for (auto v : children[u]) {
        if (v == f || visited[v]) continue;
        find_center(v, u, sum);
        size_subtree[u] += size_subtree[v];
        max_size[u] = max(max_size[u], size_subtree[v]);
    }
    max_size[u] = max(max_size[u], sum - size_subtree[u]);
    if (root == 0 || max_size[u] < max_size[root]) {
        root = u;
    }
    return;
}

void get_distances(int u, int f, int k, int d) {
    depth[u]++;
    fa[u][depth[u]] = k;
    dists[u][depth[u]] = d;
    size_subtree[u] = 1;
    for (auto v : children[u]) {
        if (v == f || visited[v]) continue;
        get_distances(v, u, k, d + 1);
        size_subtree[u] += size_subtree[v]; // 메모리 할당용 
    }
    return;
}

void ADD_FUNCTION(int u, int v, int f, int id) { // 중점 u에서의 기여값을 T[id][f]에 반영 
    for (int x = u; x < T[id][f].size(); x += (x & -x)) {
        T[id][f][x] += v;
    }
    return;
}

int QUERY_FUNCTION(int u, int id) { // 거리 u 이내의 기여값 합을 구함 
    int res = 0;
    for (int x = u; x > 0; x -= (x & -x)) {
        res += T[id][x];
    }
    return res;
}

void main_dfs(int u) { // u에 대한 DFS 
    visited[u] = 1;
    get_distances(u, 0, u, 0);
    T[0][u].resize(size_subtree[u] + 5);
    T[1][u].resize(size_subtree[u] + 5);
    for (auto v : children[u]) {
        if (visited[v]) continue;
        root = 0;
        find_center(v, 0, size_subtree[v]);
        main_dfs(root);
    }
    return;
}

void update(int u, int k) { // u의 가중치를 k로 변경 
    for (int i = depth[u]; i >= 1; --i) {
        int f = fa[u][i];
        ADD_FUNCTION(dists[u][i] + 1, k - A[u], f, 0);
        if (i > 1) {
            ADD_FUNCTION(dists[u][i - 1] + 1, k - A[u], fa[u][i + 1], 1);
        }
    }
}

int query(int u, int k) { // u에서 거리 k 이내의 답변 구하기 
    int dd, res = 0;
    for (int i = depth[u]; i >= 1; --i) {
        int f = fa[u][i];
        int f1 = fa[u][i + 1];
        int df = dists[u][i];
        if (df <= k) {
            dd = T[0][f].size() - 1;
            dd = min(dd, k - df + 1);
            res += QUERY_FUNCTION(dd, 0);
            if (f1) {
                dd = T[1][f1].size() - 1;
                dd = min(dd, k - df + 1);
                res -= QUERY_FUNCTION(dd, 1);
            }
        }
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int answer = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> B[i];
        A[i] = 0;
    }
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        ADD(a, b);
    }
    max_size[root = 0] = INF;
    find_center(1, 0, n);
    main_dfs(root);
    for (int i = 1; i <= n; ++i) {
        update(i, B[i]);
        A[i] = B[i];
    }
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        b ^= answer;
        c ^= answer;
        if (a == 1) {
            update(b, c);
            A[b] = c;
        } else {
            answer = query(b, c);
            cout << answer << endl;
        }
    }
    return 0;
}

<완료! 🎉>