Hướng dẫn cho LQDOJ CUP 2022 - Final Round - FIREWORK

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Flower_On_Stone , ldn694 , BJMinhNhut

Subtask \(1\) (\(15\%\) số điểm): \(n,m,q \leq 500\).

Tutorial

Vì \(n,m,q\) rất nhỏ, ta có thể mô phỏng y hệt mô tả đề. Với mỗi truy vấn hỏi tổng độ đẹp mắt ở địa điểm d_j, ta duyệt qua toàn bộ các loại pháo bông, nếu loại pháo bông nào được bắn trước thời điểm \(v_j\) và địa điểm bắn pháo bông đủ gần địa điểm \(d_j\) thì ta cộng vào kết quả.
Độ phức tạp: \(\mathcal{O}(n \cdot m \cdot q)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5005;
const int INF = (int)1e9;

struct Query {
    int node, beauty, influenceRange, time, id, type;

    Query(int _node = 0, int _beauty = 0, int _influenceRange = 0, int _time = 0, int _id = 0, int _type = 0) : node(_node), beauty(_beauty), influenceRange(_influenceRange), time(_time), id(_id), type(_type){};

    bool operator<(const Query &other) const {
        return time == other.time ? type < other.type : time < other.time;
    }
};

int numNode, numQuestion, numEvent;
vector<int> adj[MAX_N];
int dist[MAX_N][MAX_N];
long long total[MAX_N], result[MAX_N];
Query queries[2 * MAX_N];

void bfs(int start, int dist[]) {
    for (int node = 1; node <= numNode; node++) {
        dist[node] = INF;
    }
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int u : adj[node]) {
            if (dist[u] == INF) {
                dist[u] = dist[node] + 1;
                q.push(u);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("FIREWORK.inp", "r", stdin);
    freopen("FIREWORK.out", "w", stdout);

    cin >> numNode >> numEvent >> numQuestion;
    for (int i = 1; i < numNode; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= numEvent; i++) {
        int time, node, beauty, influenceRange;
        cin >> time >> node >> beauty >> influenceRange;
        queries[i] = Query(node, beauty, influenceRange, time, 0, 0);
    }
    for (int i = 1; i <= numQuestion; i++) {
        int time, node;
        cin >> time >> node;
        queries[i + numEvent] = Query(node, 0, 0, time, i, 1);
    }
    int numQuery = numQuestion + numEvent;
    sort(queries + 1, queries + numQuery + 1);

    for (int node = 1; node <= numNode; node++) {
        bfs(node, dist[node]);
    }
    for (int i = 1; i <= numQuery; i++) {
        if (queries[i].type == 0) {
            for (int node = 1; node <= numNode; node++) {
                if (dist[queries[i].node][node] <= queries[i].influenceRange) {
                    total[node] += queries[i].beauty;
                }
            }
        } else {
            result[queries[i].id] = total[queries[i].node];
        }
    }

    for (int i = 1; i <= numQuestion; i++) {
        cout << result[i] << "\n";
    }

    return 0;
}

Subtask \(2\) (\(15\%\) số điểm): \(n,m,q \leq 5 \cdot 10^3\).

Tutorial

Vì các truy vấn cập nhật và trả lời có thời gian (tham số \(t_i\)). Chúng ta có thể dễ dàng loại điều kiện này bằng cách xử lí offline: sort các query theo \(t\) tăng dần và xử lí lần lượt.
Từ đây, bài toán trở thành cho các truy vấn;

\(\text{update}\) \(u, c, s\): cập nhật giá trị các nút \(v\) mà \(\text{distance}(u, v) \le s\) thêm giá trị \(c\).
\(\text{get}\) \(u\): in ra giá trị hiện tại của nút \(u\)

Như vậy ta cải tiến subtask 1 bằng cách sắp xếp tất cả truy vấn và các loại pháo bông theo thứ tự thời gian tăng dần và duyệt như cũ.

Độ phức tạp: \(\mathcal{O}((m + q)\log_2(m+q) + m \cdot n)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

struct Event {
    int timeStart;
    int node;
    int influenceRange;
    int beauty;

    Event(int _timeStart = 0, int _node = 0, int _influenceRange = 0, int _beauty = 0) : timeStart(_timeStart), node(_node), influenceRange(_influenceRange), beauty(_beauty) {}

    bool operator<(const Event &other) const {
        return timeStart < other.timeStart;
    }
};

struct Question {
    int id;
    int time;
    int node;

    Question(int _id = 0, int _time = 0, int _node = 0) : id(_id), time(_time), node(_node) {}

    bool operator<(const Question &other) const {
        return time < other.time;
    }
};

int numNode, numEvent, numQuestion;
vector<int> adj[MAX_N];
Event events[MAX_N];
Question questions[MAX_N];
long long sumBeauty[MAX_N];
long long answer[MAX_N];

void update(int node, int parent, int depth, int beaty, int influenceRange) {
    if (depth > influenceRange) {
        return;
    }
    sumBeauty[node] += beaty;
    for (auto &u : adj[node]) {
        if (u != parent) {
            update(u, node, depth + 1, beaty, influenceRange);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("FIREWORK.inp", "r", stdin);
    freopen("FIREWORK.out", "w", stdout);

    cin >> numNode >> numEvent >> numQuestion;
    for (int i = 1; i < numNode; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= numEvent; i++) {
        cin >> events[i].timeStart >> events[i].node >> events[i].beauty >> events[i].influenceRange;
    }
    for (int i = 1; i <= numQuestion; i++) {
        cin >> questions[i].time >> questions[i].node;
        questions[i].id = i;
    }
    sort(events + 1, events + numEvent + 1);
    sort(questions + 1, questions + numQuestion + 1);

    int cntEvent = 1;
    for (int i = 1; i <= numQuestion; i++) {
        while (cntEvent <= numEvent && events[cntEvent].timeStart <= questions[i].time) {
            update(events[cntEvent].node, -1, 0, events[cntEvent].beauty, events[cntEvent].influenceRange);
            cntEvent++;
        }
        answer[questions[i].id] = sumBeauty[questions[i].node];
    }

    for (int i = 1; i <= numQuestion; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

Subtask \(3\) (\(15\%\) số điểm): \(a_i = i, b_i = i + 1, \forall 1 \leq i < n\).

Tutorial

Khi cây có dạng đường thẳng, bài toán trở thành một bài toán kinh điển về Cấu trúc dữ liệu: Cho dãy số \(n\) phần tử và các truy vấn:

\(\text{update}\) \(u, c, s\): cập nhật giá trị các phần tử trong đoạn \([\max(1, u-s), \min(n, u+s)]\) thêm giá trị \(c\).
\(\text{get}\) \(u\): in ra giá trị hiện tại của phần tử \(u\)

Ta có thể dễ dàng giải bằng cách dùng Lazy Segment Tree hoặc Fenwick Tree.
Độ phức tạp: \(\mathcal{O}((m+q)\log(m+q) + q\log n)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

struct Event {
    int timeStart;
    int node;
    int influenceRange;
    int beauty;

    Event(int _timeStart = 0, int _node = 0, int _influenceRange = 0, int _beauty = 0) : timeStart(_timeStart), node(_node), influenceRange(_influenceRange), beauty(_beauty) {}

    bool operator<(const Event &other) const {
        return timeStart < other.timeStart;
    }
};

struct Question {
    int id;
    int time;
    int node;

    Question(int _id = 0, int _time = 0, int _node = 0) : id(_id), time(_time), node(_node) {}

    bool operator<(const Question &other) const {
        return time < other.time;
    }
};

struct FenwickTree {
    int treeSize;
    vector<long long> nodes;

    void init(int treeSize) {
        this->treeSize = treeSize;
        nodes.assign(treeSize + 1, 0);
    }

    void update(int id, long long val) {
        for (; id <= treeSize; id += (id & -id)) {
            nodes[id] += val;
        }
    }

    long long get(int id) {
        long long result = 0;
        for (; id >= 1; id -= (id & -id)) {
            result += nodes[id];
        }
        return result;
    }
};

int numNode, numEvent, numQuestion;
vector<int> adj[MAX_N];
Event events[MAX_N];
Question questions[MAX_N];
FenwickTree sumBeauty;
long long answer[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("FIREWORK.inp", "r", stdin);
    freopen("FIREWORK.out", "w", stdout);

    cin >> numNode >> numEvent >> numQuestion;
    for (int i = 1; i < numNode; i++) {
        int u, v;
        cin >> u >> v;
        assert(u == i && v == i + 1);
    }
    for (int i = 1; i <= numEvent; i++) {
        cin >> events[i].timeStart >> events[i].node >> events[i].beauty >> events[i].influenceRange;
    }
    for (int i = 1; i <= numQuestion; i++) {
        cin >> questions[i].time >> questions[i].node;
        questions[i].id = i;
    }
    sort(events + 1, events + numEvent + 1);
    sort(questions + 1, questions + numQuestion + 1);

    int cntEvent = 1;
    sumBeauty.init(numNode);
    for (int i = 1; i <= numQuestion; i++) {
        while (cntEvent <= numEvent && events[cntEvent].timeStart <= questions[i].time) {
            sumBeauty.update(max(1, events[cntEvent].node - events[cntEvent].influenceRange), events[cntEvent].beauty);
            sumBeauty.update(events[cntEvent].node + events[cntEvent].influenceRange + 1, -events[cntEvent].beauty);
            cntEvent++;
        }
        answer[questions[i].id] = sumBeauty.get(questions[i].node);
    }

    for (int i = 1; i <= numQuestion; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

Subtask \(4\) (\(20\%\) số điểm): \(s_i = 1, \forall 1 \leq i \leq m\).

Tutorial

Ta có nhận xét, với \(s_i = 1\), truy vấn cập nhật của chúng ta chỉ cập nhật 1 đỉnh và các đỉnh kề của nó, bao gồm cha trực tiếp của nó và các đỉnh con trực tiếp của nó.

Việc cập nhật chính bản thân mình và cha trực tiếp có thể thực hiện trong \(O(1)\) vô cùng đơn giản, nhưng các đỉnh con của nó thì không thể cập nhật riêng lẻ như bình thường được. Do đó, ta sẽ lưu một mảng \(\text{lazy}\) với \(\text{lazy}[u]\) là tổng giá trị mà các đỉnh con của \(u\) cần được cộng thêm. Khi ta cần lấy giá trị một đỉnh \(u\) nào đó, ta chỉ cần cộng thêm \(\text{lazy}[parent[u]]\) với \(parent[u]\) là nút cha của \(u\) (nếu có). Ta có thể chuẩn bị trước \(parent[u]\) bằng một lần gọi DFS.

Độ phức tạp: \(\mathcal{O}((m+q) \log(m+q))\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

struct Event {
    int timeStart;
    int node;
    int influenceRange;
    int beauty;

    Event(int _timeStart = 0, int _node = 0, int _influenceRange = 0, int _beauty = 0) : timeStart(_timeStart), node(_node), influenceRange(_influenceRange), beauty(_beauty) {}

    bool operator<(const Event &other) const {
        return timeStart < other.timeStart;
    }
};

struct Question {
    int id;
    int time;
    int node;

    Question(int _id = 0, int _time = 0, int _node = 0) : id(_id), time(_time), node(_node) {}

    bool operator<(const Question &other) const {
        return time < other.time;
    }
};

int numNode, numEvent, numQuestion;
vector<int> adj[MAX_N], bigAdj[MAX_N];
Event events[MAX_N];
Question questions[MAX_N];
long long answer[MAX_N], dp[MAX_N], lazy[MAX_N];
int parent[MAX_N];

void dfs(int node) {
    for (auto &u : adj[node]) {
        if (u != parent[node]) {
            parent[u] = node;
            dfs(u);
        }
    }
}

void update(int node, int beauty) {
    dp[node] += beauty;
    lazy[parent[node]] += beauty;
}

long long get(int node) {
    return dp[node] + lazy[node] + dp[parent[node]];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("FIREWORK.inp", "r", stdin);
    freopen("FIREWORK.out", "w", stdout);

    cin >> numNode >> numEvent >> numQuestion;
    for (int i = 1; i < numNode; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= numEvent; i++) {
        cin >> events[i].timeStart >> events[i].node >> events[i].beauty >> events[i].influenceRange;
        assert(events[i].influenceRange == 1);
    }
    for (int i = 1; i <= numQuestion; i++) {
        cin >> questions[i].time >> questions[i].node;
        questions[i].id = i;
    }
    dfs(1);
    sort(events + 1, events + numEvent + 1);
    sort(questions + 1, questions + numQuestion + 1);

    int cntEvent = 1;
    for (int i = 1; i <= numQuestion; i++) {
        while (cntEvent <= numEvent && events[cntEvent].timeStart <= questions[i].time) {
            update(events[cntEvent].node, events[cntEvent].beauty);
            cntEvent++;
        }
        answer[questions[i].id] = get(questions[i].node);
    }

    for (int i = 1; i <= numQuestion; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

Subtask \(5\) (\(20\%\) số điểm): \(s_i = 2, \forall 1 \leq i \leq m\).

Tutorial

Do tất cả \(m\) loại pháo hoa có độ ảnh hưởng đều bằng \(2\), ta nhận thấy để trả lời truy vấn tại một nút \(u\), ta cần lấy thông tin từ các có khoảng cách tới \(u\) là \(1\), \(2\), và thông tin từ chính nút \(u\).

Như các subtask trước, ta sắp xếp các truy vấn. Gọi \(dp[u][x]\) là tổng độ đẹp mắt của các loại pháo hoa đặt tại các nút con của \(u\) có khoảng cách tới \(u\) là \(x\).

Để cập nhật pháo hoa tại nút \(u\) với độ đẹp mắt là \(c\), ta đơn giản cập nhật tăng \(dp[u][0]\), \(dp[parent[u]][1]\), \(dp[parent[parent[u]]][2]\) thêm \(c\) đơn vị.

Để trả lời truy vấn tại nút \(u\) bất kì, ta có các trường hợp sau:

\(dp[u][0] + dp[u][1] + dp[u][2]\): tổng độ đẹp mắt tại các nút thuộc cây con gốc \(u\), có khoảng cách tới \(u\) tối đa là \(2\).
\(dp[parent[u]][1] - dp[u][0] + dp[parent[u]][0]\): tổng độ đẹp mắt tại nút cha của \(u\) và các nút anh em của \(u\), cộng vào đáp án nếu \(parent[u]\) tồn tại.
\(dp[parent[parent[u]]][2]\): tổng độ đẹp mắt tại nút tổ tiên thứ \(2\) của \(u\), cộng vào đáp án nếu tổ tiên thứ \(2\) của \(u\) tồn tại.

Độ phức tạp: \(\mathcal{O}((m + q) \log(m + q))\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;

struct Event {
    int timeStart;
    int node;
    int influenceRange;
    int beauty;

    Event(int _timeStart = 0, int _node = 0, int _influenceRange = 0, int _beauty = 0) : timeStart(_timeStart), node(_node), influenceRange(_influenceRange), beauty(_beauty) {}

    bool operator<(const Event &other) const {
        return timeStart < other.timeStart;
    }
};

struct Question {
    int id;
    int time;
    int node;

    Question(int _id = 0, int _time = 0, int _node = 0) : id(_id), time(_time), node(_node) {}

    bool operator<(const Question &other) const {
        return time < other.time;
    }
};

int numNode, numEvent, numQuestion;
vector<int> adj[MAX_N], bigAdj[MAX_N];
Event events[MAX_N];
Question questions[MAX_N];
long long answer[MAX_N], dp[MAX_N][3];
int parent[MAX_N];

void dfs(int node) {
    for (auto &u : adj[node]) {
        if (u != parent[node]) {
            parent[u] = node;
            dfs(u);
        }
    }
}

void update(int node, int beauty) {
    dp[node][0] += beauty;
    dp[parent[node]][1] += beauty;
    dp[parent[parent[node]]][2] += beauty;
}

long long get(int node) {
    long long result = dp[node][0] + dp[node][1] + dp[node][2];
    if (parent[node]) {
        result += dp[parent[node]][1] - dp[node][0] + dp[parent[node]][0];
    }
    if (parent[parent[node]]) {
        result += dp[parent[parent[node]]][0];
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("FIREWORK.inp", "r", stdin);
    freopen("FIREWORK.out", "w", stdout);

    cin >> numNode >> numEvent >> numQuestion;
    for (int i = 1; i < numNode; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= numEvent; i++) {
        cin >> events[i].timeStart >> events[i].node >> events[i].beauty >> events[i].influenceRange;
        assert(events[i].influenceRange == 2);
    }
    for (int i = 1; i <= numQuestion; i++) {
        cin >> questions[i].time >> questions[i].node;
        questions[i].id = i;
    }
    dfs(1);
    sort(events + 1, events + numEvent + 1);
    sort(questions + 1, questions + numQuestion + 1);

    int cntEvent = 1;
    for (int i = 1; i <= numQuestion; i++) {
        while (cntEvent <= numEvent && events[cntEvent].timeStart <= questions[i].time) {
            update(events[cntEvent].node, events[cntEvent].beauty);
            cntEvent++;
        }
        answer[questions[i].id] = get(questions[i].node);
    }

    for (int i = 1; i <= numQuestion; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

Subtask \(6\) (\(15\%\) số điểm): Không có ràng buộc gì thêm.

Tutorial

Nhận xét

Với dạng bài toán này, chúng ta có thể thực hiện bằng thuật toán Centroid Decomposition cộng với cấu trúc dữ liệu (Fenwick Tree hoặc Trie hoặc Segment Tree).

Thuật toán

Đầu tiên ta sắp xếp các truy vấn. Trước khi thực hiện các truy vấn, chúng ta dựng ra cây centroid, với tính chất độ cao tối đa của cây centroid là \(\log_2 n\), ta có thể cập nhật và lấy giá trị trong thời gian khá tốt.

Tính chất của cây centroid : khi \(p\) là LCA (Lowest Common Ancestor) của \(u\) và \(v\) trên cây centroid, thì \(p\) nằm trên đường đi từ \(u\) đến \(v\) trên cây gốc. Tương đương với việc \(\text{distance}(u, p)\) \(+\) \(\text{distance}(v, p)\) \(=\) \(\text{distance}(u, v)\). Chúng ta nên tính trước \(\text{distance}(u, parent)\) với tất cả \(parent\) là tổ tiên của \(u\) trên cây centroid.

Để quản lí điều kiện trên, chúng ta dùng đến một cấu trúc dữ liệu cho phép :

\(\text{update}\) \(i, val :\) cập nhật mọi vị trí \(\le i\) lên một giá trị \(val\).
\(\text{get}\) \(i :\) lấy giá trị tại vị trí \(i\).

Cây Fenwick Tree là một cấu trúc dữ liệu phù hợp:

Với việc cập nhật (\(u, c, s\)), ta xuất phát từ \(u\), đi lên các tổ tiên centroid của \(u\), giả sử đang đứng ở \(p\), thực hiện truy vấn (\(\text{update}\) \(s - \text{distance}(u, p)\), \(c\)) trên cây Fenwick Tree của nút \(p\).
Còn việc lấy giá trị nút \(u\), ta cũng đi dần lên các tổ tiên centroid của \(u\), và thực hiện \(\text{get}\) \(\text{distance}(u, p)\) trên cây Fenwick Tree của \(p\)
Gọi \(f(u)\) là giá trị lớn nhất của \(\text{distance}(u, v)\) với mọi \(v\) thuộc cây con của \(u\) trên cây centroid. Từ nhận xét truy vấn get, ta có thể thấy đối với nút \(u\) chỉ cần tạo cây Fenwick Tree có kích thước là \(f(u)\). Ta có tính chất \(\sum_{i = 1}^{n}f(i)\) \(\le\) \(n\log_2 n\) (chứng minh nhường lại cho bạn đọc), nên việc tạo \(n\) cây Fenwick Tree nằm trong sự cho phép.

Nhưng vẫn còn một vấn đề ta cần giải quyết, một cặp \((u, v)\) có thể tính lại nhiều lần. Gọi \(\text{lca}(u, v)\) trên centroid là \(p\), cha của \(p\) đặt là \(g\), cặp \((u, v)\) sẽ bị tính trùng khi \(\text{distance}(u, p)\) \(+\) \(\text{distance}(p, v)\) \(\le\) \(s\) và \(\text{distance}(u, g)\) + \(\text{distance}(g, v)\) \(\le\) \(s\). Để trừ phần trùng, mỗi nút trên cây cần thêm một cây Fenwick Tree nữa, thực hiện tương tự như trên (bạn đọc suy nghĩ kĩ). Cây Fenwick Tree thứ 2 ở nút \(u\) có kích thước là \(d(u)\), với \(d(u)\) là giá trị lớn nhất của \(\text{distance}(v, p)\) với \(p\) là cha của \(u\) trên cây centroid, và \(v\) là một con bất kì của \(u\) trên centroid. Ta vẫn có tính chất \(\sum_{i = 1} ^ {n}d(i)\) \(\le\) \(n \log_2 (n)\) (chứng minh xin nhường bạn đọc).

Độ phức tạp: \(\mathcal{O}(n \log^2n)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int LOG = 18;

struct Event {
    int timeStart;
    int node;
    int influenceRange;
    int beauty;

    Event(int _timeStart = 0, int _node = 0, int _influenceRange = 0, int _beauty = 0) : timeStart(_timeStart), node(_node), influenceRange(_influenceRange), beauty(_beauty) {}

    bool operator<(const Event &other) const {
        return timeStart < other.timeStart;
    }
};

struct Question {
    int id;
    int time;
    int node;

    Question(int _id = 0, int _time = 0, int _node = 0) : id(_id), time(_time), node(_node) {}

    bool operator<(const Question &other) const {
        return time < other.time;
    }
};

struct FenwickTree {
    int treeSize;
    vector<long long> nodes;

    FenwickTree(int treeSize = 0) {
        this->treeSize = treeSize;
        nodes.assign(treeSize + 2, 0);
    }

    void update(int id, long long val) {
        id = min(id, treeSize);
        id = treeSize - id + 1;
        for (; id <= treeSize + 1; id += (id & -id)) {
            nodes[id] += val;
        }
    }

    long long get(int id) {
        long long result = 0;
        id = treeSize - id + 1;
        for (; id >= 1; id -= (id & -id)) {
            result += nodes[id];
        }
        return result;
    }
} fenwickTree[MAX_N], cnt[MAX_N];

int numNode, numEvent, numQuestion;
vector<int> adj[MAX_N];
Event events[MAX_N];
Question questions[MAX_N];
int treeSize[MAX_N], weight[MAX_N];
bool done[MAX_N];
int dist[MAX_N][LOG];
int centroidParent[MAX_N], centroidDepth[MAX_N];
long long answer[MAX_N];

void dfsSize(int node, int parent) {
    treeSize[node] = 1;
    for (auto &u : adj[node]) {
        if (!done[u] && u != parent) {
            dfsSize(u, node);
            treeSize[node] += treeSize[u];
        }
    }
}

int findCentroid(int node, int parent, int lim) {
    for (auto &u : adj[node]) {
        if (!done[u] && u != parent && treeSize[u] * 2 > lim) {
            return findCentroid(u, node, lim);
        }
    }
    return node;
}

int maxDepth, maxParentDepth;

void dfs(int node, int parent, int level) {
    maxParentDepth = max(maxParentDepth, dist[node][level - 1]);
    for (auto &u : adj[node]) {
        if (!done[u] && u != parent) {
            dist[u][level] = dist[node][level] + 1;
            maxDepth = max(maxDepth, dist[u][level]);
            dfs(u, node, level);
        }
    }
}

void buildCentroid(int node, int parent, int level) {
    dfsSize(node, parent);
    int centroid = findCentroid(node, parent, treeSize[node]);
    centroidParent[centroid] = parent;
    centroidDepth[centroid] = level;
    maxDepth = 0;
    maxParentDepth = 0;
    dist[centroid][level] = 0;
    dfs(centroid, -1, level);
    fenwickTree[centroid] = FenwickTree(maxDepth);
    cnt[centroid] = FenwickTree(maxParentDepth);
    done[centroid] = true;
    for (auto &node : adj[centroid]) {
        if (!done[node]) {
            buildCentroid(node, centroid, level + 1);
        }
    }
}

void update(int current_node, int node, int influenceRange, int beauty, int depth) {
    if (dist[node][depth] <= influenceRange) {
        fenwickTree[current_node].update(influenceRange - dist[node][depth], beauty);
    }
    if (depth > 1) {
        int parent = centroidParent[current_node];
        if (dist[node][depth - 1] <= influenceRange) {
            cnt[current_node].update(influenceRange - dist[node][depth - 1], beauty);
        }
        update(parent, node, influenceRange, beauty, depth - 1);
    }
}

long long get(int current_node, int node, int depth) {
    long long result = fenwickTree[current_node].get(dist[node][depth]);
    if (depth > 1) {
        int parent = centroidParent[current_node];
        result -= cnt[current_node].get(dist[node][depth - 1]);
        result += get(parent, node, depth - 1);
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("FIREWORK.inp", "r", stdin);
    freopen("FIREWORK.out", "w", stdout);

    cin >> numNode >> numEvent >> numQuestion;
    for (int i = 1; i < numNode; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    buildCentroid(1, -1, 1);
    for (int i = 1; i <= numEvent; i++) {
        cin >> events[i].timeStart >> events[i].node >> events[i].beauty >> events[i].influenceRange;
    }
    for (int i = 1; i <= numQuestion; i++) {
        cin >> questions[i].time >> questions[i].node;
        questions[i].id = i;
    }
    sort(events + 1, events + numEvent + 1);
    sort(questions + 1, questions + numQuestion + 1);

    int cntEvent = 1;
    for (int i = 1; i <= numQuestion; i++) {
        while (cntEvent <= numEvent && events[cntEvent].timeStart <= questions[i].time) {
            update(events[cntEvent].node, events[cntEvent].node, events[cntEvent].influenceRange, events[cntEvent].beauty, centroidDepth[events[cntEvent].node]);
            cntEvent++;
        }
        answer[questions[i].id] = get(questions[i].node, questions[i].node, centroidDepth[questions[i].node]);
    }

    for (int i = 1; i <= numQuestion; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

Bình luận

Không có bình luận nào.