Subtask 1: ~n, m, q \leq 500~

Với subtask 1, do giới hạn nhỏ, ta có thể cài thuật trâu. Chuẩn bị mảng lưu thứ tự DFS của cây, ~tin(u)~ và ~tout(u)~ là thời điểm bắt đầu duyệt đỉnh ~u~ và kết thúc duyệt đỉnh ~u~. Với mỗi truy vấn ~{L_i, R_i, u_i}~ trong ~q~ truy vấn, ta sẽ thử thực thi từng công việc một. Với mỗi công việc ~t~ từ ~L_i~ đến ~R_i~, ta sẽ cần tăng những đỉnh trong cây con của ~u_t~ lên ~w_t~ đơn vị, việc này có thể làm nhanh nhờ mảng hiệu. Ta cộng ~w_t~ cho ~tin(u_t)~ và trừ ~w_t~ cho ~tout(u_t) + 1~. Sau đó ta tính tổng cộng dồn cho mảng thứ tự DFS, giá trị của ~tin(u_i)~ sẽ cho biết kết quả của truy vấn. Sau đó cập nhật lại mảng như ban đầu để xử lý truy vấn tiếp theo.

Độ phức tạp: ~O(q \cdot (2 \cdot m + n))~

Subtask 2: ~L_i = 1, R_i = m~ (~i = 1, \ldots, q~)

Với subtask 2, do mọi đoạn ~[L_i, R_i]~ chính là đoạn ~[1, m]~ nên ta sẽ thực hiện hết các phương án từ 1 đến m, sử dụng mảng hiệu tương tự subtask 1. Với mỗi truy vấn chỉ việc lấy giá trị của ~tin(u_i)~.

Độ phức tạp: ~O(m + n + q)~

Subtask 3: ~n, m, q \leq 5000~

Với subtask 3, ta sẽ làm tương tự subtask 1 nhưng sẽ cải tiến mảng hiệu bằng cách sử dụng cấu trúc dữ liệu cây BIT, việc cộng ~w_t~ cho ~tin(u_t)~ và trừ ~w_t~ cho ~tout(u_t) + 1~ và cập nhật lại toàn bộ mảng cộng dồn chỉ mất log. Chú ý ta cần cập nhật lại mảng về ban đầu sau khi thử từng phương án.

Độ phức tạp: ~O(q \cdot (2 \cdot m \cdot \log n))~

Subtask 4 & 5: Cây là đường thẳng / Full

Về cơ bản 2 subtask này không khác nhau là mấy, vì về cơ bản ta đã trải phẳng cây thành một mảng nên nếu làm được cho cây là đường thẳng thì cũng có thể làm cho trường hợp cây bình thường. Để ý rằng giá trị của ~u_i~ khi thực hiện các phương án từ ~L_i~ tới ~R_i~ sẽ chính là hiệu của giá trị của ~u_i~ tại thời điểm thực hiện phương án ~R_i~ cho giá trị đó khi ở thời điểm thực hiện phương án ~L_i - 1~. Gọi ~get(X)~ là giá trị của ~u_i~ tại thời điểm ~X~ thì ta sẽ cần tính được ~get(R_i) - get(L_i - 1)~.

Để làm được điều này, ta sẽ thực hiện các phương án lần lượt từ 1 đến ~m~. Với mỗi truy vấn có ~(L_j - 1)~ = vị trí ~i~ đang duyệt, ta sẽ tính được giá trị cần trừ cho truy vấn đó, cụ thể ~minus(id) = get(u_i)~ tại thời điểm đó với ~minus(id)~ là giá trị ~get(L_j - 1)~ ta sẽ trừ đi và ~id~ là số hiệu của truy vấn. Tương tự, với mỗi truy vấn có ~R_j =~ vị trí ~i~ đang duyệt~ thì ~add(id) = get(u_i)~. Sau đó với mỗi truy vấn, đáp án sẽ là ~add(id) - minus(id)~.

Ngoài ra, các bạn có thể sử dụng cách khác như persistent BIT, giúp lấy lại trạng thái mảng tại các thời điểm, tuy nhiên cách làm này sẽ không tối ưu bằng tư duy phía trên.

Độ phức tạp: ~O(m \cdot \log n + 2 \cdot q \cdot \log n)~

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
const int N = 1e5+5;
int tin[N], tout[N], bit[N], ans[N], minu[N], add[N];
vector<int> adj[N];
int tim = 0;

void update(int u, int v) {
    for (; u < N; u += u & (-u)) bit[u] += v;
}

int get(int u) {
    int res = 0;
    for (; u; u -= u & (-u)) res += bit[u];
    return res;
}

void dfs(int node, int pa) {
    tim++;
    tin[node] = tim;
    for (auto child : adj[node]) {
        if (child != pa) dfs(child, node);
    }
    tout[node] = tim;
}

int w[N], u[N];
struct query {
    int x, y, z;
};

vector<pair<int, int>> atL[N], atR[N];
vector<query> LMAO;

signed main() {
    fast
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 2; i <= n; i++) {
        int x; cin >> x;
        adj[x].pb(i);
        adj[i].pb(x);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++) cin >> u[i] >> w[i];
    for (int i = 1; i <= q; i++) {
        int L, R, node; cin >> L >> R >> node;
        atR[R].pb({node, i});
        atL[L-1].pb({node, i});
    }
    for (int i = 1; i <= m; i++) {
        update(tin[u[i]], w[i]);
        update(tout[u[i]] + 1, -w[i]);
        for (auto X : atL[i]) minu[X.second] = get(tin[X.first]);
        for (auto X : atR[i]) add[X.second] = get(tin[X.first]);
    }
    for (int i = 1; i <= q; i++) cout << add[i] - minu[i] << "\n";
}