Bài này ta sẽ sử dụng kỹ thuật difference array nhưng sử dụng trên cây.

Ta chuẩn bị mảng ~f[u]~ được dùng để update đoạn. Giả sử ta muốn tăng giá trị từ các đỉnh ~u~ tới ~v~ lên ~x~:

• ~f[u]~ và ~f[v]~ cùng cộng lên cho ~x~
• ~f[LCA(u, v)]~ phải trừ cho ~x~

Khi muốn biết được giá trị thật thì ta sẽ tính tổng giá trị của cây con từng node. Nếu thực hiện liên tục như vậy với mỗi truy vấn thì ta sẽ được một thuật toán độ phức tạp ~O(N \times Q)~ và lấy được ~20\%~ số test.

Để cải tiến thì ta phải nghĩ một cách để tính tổng giá trị của cây con nhanh hơn. Điều này có thể làm bằng một cây phân đoạn và euler tour.

Độ phức tạp: ~O(N \times log(N))~

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

void add(int& a, int b) {
    if ((a += b) >= MOD) a -= MOD;
}

void sub(int& a, int b) {
    if ((a -= b) < 0) a += MOD;
}

const int N = 1e5 + 5;
int n, root, par[N], res[N];
int now, tin[N], tout[N], FT[N];
vector<int> g[N];

void dfs(int u) {
    tin[u] = ++now;
    for (auto v : g[u]) dfs(v);
    tout[u] = now;
}

void update(int i, int val) {
    for (; i <= n; i += i & -i) add(FT[i], val);
}

int query(int l, int r) {
    int res = 1;
    l--;
    for (; l; l -= l & -l) sub(res, FT[l]);
    for (; r; r -= r & -r) add(res, FT[r]);
    return res;
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

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

    cin >> n;
    for1(i,1,n) {
        cin >> par[i];
        if (par[i] == 0) root = i;
        else g[par[i]].push_back(i);
    }

    dfs(root);
    for1(i,1,n) {
        int v; cin >> v;
        int x = query(tin[v], tout[v]);
        res[v] = x;
        if (par[v] != 0) update(tin[par[v]], x);
    }

    for1(i,1,n) cout << res[i] << " ";

}