---
author: Thienhx
tags: Contest solution
title: MaskTech Open 2024 - Editorial
license: Public domain
---

$\Huge \text{MaskTech Open 2024 - Editorial}$

------

:::info
>✍🏻Writer: [@Thienhx](https://hackmd.io/@Thienhx), [@HoangViet](https://hackmd.io/@hoangviet56), [@MinhTu](https://hackmd.io/@DjT43Y-fRqObyceoxHQWxg), [@XuanNguyen](https://hackmd.io/@Nguyencter)
>📋Content:
>[TOC]
>
>[color=blue]
:::

------

## A. Máy chấm

:::spoiler Editorial
:::info
> Với thời gian là $T$ giây thì máy chấm thứ $i$ có thể chấm được $\lfloor \frac{T}{a_i} \rfloor$ bài nộp.
> Chặt nhị phân và với mỗi thời gian là $T$ giây thì số bài nộp có thể chấm được với $N$ máy chấm là $S = \sum_{i = 1}^{n}\lfloor \frac{T}{a_i} \rfloor$.
> Nếu $S \geq K$ thì có thể chấm hết tất cả bài nộp với $T$ giây.
> Lưu ý ta chỉ cần kiểm tra xem $S$ có lớn hơn hoặc bằng $K$ hay không nên chỉ for tính $S$ tiếp khi $S$ hiện tại đang nhỏ hơn $K$ để tránh trường hợp tràn số.
>
> Độ phức tạp $O(N$ * $log(10^{18}))$.
:::

:::spoiler Solution

#include <bits/stdc++.h>

#define ll long long 
#define fi first 
#define se second 

using namespace std;

const int MAXN = 3e5 + 1;
const ll INF = 1e18;
const int MOD = 998244353;

ll n, k, a[MAXN];

bool check(ll time) {
    ll res = 0;
    for(int i = 1; i <= n; i ++) {
        res += (time / a[i]);
        if(res >= k) return true;
    }
    return false;
}

void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    ll l = 0, r = INF, mid, ans;
    while(l <= r) {
        mid = (l + r) / 2;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }

    cout << ans << '\n';
}

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

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    // int tt;
    // cin >> tt;
    // while(tt --)
        solve();

    return 0;
}

:::

------

## B. Chiến tranh

:::spoiler Tóm tắt đề
>Ta được cho một đồ thị dạng cây có $N$ đỉnh, trong đó đỉnh $i$ ban đầu có trọng số là $a_i$.
>Tìm sô lượng cặp $u, v$ $(u \leq v)$ sao cho tổng trọng số các đỉnh nằm trên đường đi từ $u$ đến $v$ có dạng $2^k - 1$ với $k$ là một số nguyên dương.
:::

### Sub 1

:::spoiler Editorial
:::info
>$N \leq 500$
>
> Có thể dùng thuật toán $floyd$ để tính $sum[u][v]$ là tổng trọng số từ đỉnh $u$ đến $v$.
> Thử tất cả các cặp $u, v$ với mỗi cặp thì for xem $sum[u][v]$ có thuộc dạng $2^k - 1$ hay không.
>
> Độ phức tạp $O(N^3)$.
:::

### Sub 2

:::spoiler Editorial
:::info
>$N \leq 5000$
>
> Nhận thấy $\sum_{i = 1}^{n}a_i$ không quá $10^7$, nên ta có thể chuẩn bị trước để kiểm tra một số có dạng $2^k - 1$ hay không trong $O(1)$.
> Với mỗi đỉnh $u$ ta sẽ $DFS$ qua các đỉnh còn lại bắt đầu từ đỉnh $u$ và tỉnh tổng trong quá trình gọi hàm $DFS$.
>
> Độ phức tạp $O(N^2)$.
:::

:::spoiler Solution

#include <bits/stdc++.h>

#define ll long long 
#define fi first 
#define se second 

using namespace std;

const int MAXN = 1e4 + 10;
const int MOD = 998244353;
const int INF = 1e7 + 100;

int n, a[MAXN], ans;
vector<int> adj[MAXN];
bool check[INF];

void DFS(int u, int par, int cost, int root) {
    ans += (check[cost] && root <= u);

    for(auto v : adj[u])
        if(v != par)
            DFS(v, u, cost + a[v], root);
}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    for(int i = 1; i < n; i ++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    memset(check, false, sizeof(check));
    for(int i = 1; (1 << i) - 1 < INF; i ++)
        check[(1 << i) - 1] = true;

    ans = 0;
    for(int i = 1; i <= n; i ++)
        DFS(i, i, a[i], i);

    cout << ans << '\n';
}

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

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    // int tt;
    // cin >> tt;
    // while(tt --)
        solve();

    return 0;
}

:::

------

## C. Thắp sáng

### Sub 1

:::spoiler Editorial
:::info
>$K \leq 20$
>
> Với $K \leq 20$ thì ta sẽ thử tất cả các cách chọn. Với mỗi cách, ta kiểm tra xem các đoạn được chọn có bao phủ toàn bộ bảng hay không. Nếu có thì cập nhật kết quả.
>
> ĐPT bài toán: $O(2^K * N)$
:::

### Sub 2

:::spoiler Editorial
:::info
>$c_1 = c_2 = c_3 = ... = c_N$
>
>Bởi vì giá tiền của các bóng đèn bằng nhau từng đôi một nên cách làm của ta sẽ là tham lam mua càng ít bóng đèn càng tốt. Gọi $best_i$ là vị trí xa nhất bên phải vị trí $i$ mà $[i...best_i]$ là một trong $K$ đoạn thẳng mà bài cho. Gọi $cur$ là vị trí xa nhất bên phải sao cho ta đã thắp sáng được cả đoạn từ $1$ đến $cur$. Do là ta đã thắp sáng được các vị trí từ $1$ đến $cur$ rồi nên đoạn tiếp theo mà ta sẽ lấy sẽ có đầu mút trái thuộc đoạn $[1...cur + 1]$ và đầu mút phải càng xa càng tốt. Ta có thể tìm đầu mút phải bằng cách giữ một biến $mx$ trong quá trình duyệt.
>
>ĐPT bài toán: $O(n)$
:::

:::spoiler Solution

    cin >> n >> k;

    for(int i = 1; i <= k; i++) {
        int l, r; cin >> l >> r;
        ll c; cin >> c;
        adj[r].push_back({l, c});
        val.push_back(c);
    }

    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end()) - val.begin());

    if(val.size() == 1) {
        int best[n + 1] = {0};
        for(int i = 1; i <= n; i++) {
            for(pair<int, int> x : adj[i]) {
                int j = x.fi;
                best[j] = max(best[j], i);
            }
        }        

        int cnt = 0, cur = 0, mx = 0;
        for(int i = 1; i <= cur + 1; i++) {
            if(i > n) break;
            mx = max(mx, best[i]);
            if(i == cur + 1) cur = mx, mx = 0, cnt++;
        }

        cout << cnt * val[0] << '\n';
        return;
    }

:::

### Sub 3

:::spoiler Editorial
:::info
>$N \leq 5000$
>
>Gọi $dp_r$ là giá tiền mua tối thiểu để thắp sáng tất cả các vị trí từ $1$ đến $r$. Với mỗi vị trí $r$, ta chuyển trạng thái như sau: $dp_r = min(dp_r, min(dp_{l-1}, cur) + cost)$. Với $cur$ là giá trị $dp_j$ nhỏ nhất với $j$ nằm trong đoạn từ $l$ đến $r$ và $cost$ là giá tiền của đoạn $[l, r]$.
>
>Ta duyệt vị trí $r$ mất độ phức tạp $O(n)$ và với mỗi $l,r$ ta lại tìm $cur$ mất thêm $O(r-l+1)$ nữa nên độ phức tạp tổng của ta sẽ là $O(n ^ 2)$
:::

:::spoiler solution

#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define db  double
#define vl  vector<ll>
#define pll  pair<ll, ll>
#define vpll  vector<pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define BIT(x, i) (((x) >> (i)) & 1) 

int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int mod[] = {(int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9+ 9277};
const double eps = 1e-9;
const int LOG = 17;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

// ---------------------------------------- 
const int maxn = 1e5 + 777;
int n, k;
vector<pair<int, ll>> adj[maxn];
ll dp[maxn], pre[maxn];

void solve() {
    memset(pre, 0, sizeof(pre));
    cin >> n >> k;

    for(int i = 1; i <= k; i++) {
        int l, r; cin >> l >> r;
        ll c; cin >> c;
        adj[r].pb({l, c});
        pre[l]++, pre[r + 1]--;
    }

    for(int i = 1; i <= n; i++)
        pre[i] += pre[i - 1];
    for(int i = 1; i <= n; i++) 
        if(pre[i] == 0) {
            cout << "Impossible" << '\n';
            return;
        }
    
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;

    for(int i = 1; i <= n; i++) {
        for(pair<int, ll> tmp : adj[i]) {
            int l = tmp.fi, r = i, cost = tmp.se;

            for(int j = l; j <= r; j++) 
                dp[i] = min(dp[i], min(dp[l - 1], dp[j]) + cost);
        }
    }

    cout << dp[n] << '\n';
}

int main(){ 
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    bool ok = false;
    if(ok) {
        int t; cin >> t;
        while(t--)  solve();
    }   
    else
        solve();
}

:::

### Sub 4

:::spoiler Editorial
:::info
>Không có ràng buộc gì thêm
>
>Làm tương tự như $subtask$ $3$, ta tối ưu hóa việc tìm $cur$ bằng cách sử dụng cấu trúc dữ liệu $Segment$ $Tree$. ĐPT cuối cùng là $O(n * log(n))$
:::

:::spoiler Solution

#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define db  double
#define vl  vector<ll>
#define pll  pair<ll, ll>
#define vpll  vector<pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define BIT(x, i) (((x) >> (i)) & 1) 

int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int mod[] = {(int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9+ 9277};
const double eps = 1e-9;
const int LOG = 17;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

// ---------------------------------------- 
const int maxn = 1e5 + 777;
int n, k;
vector<pair<int, ll>> adj[maxn];
ll dp[maxn], seg[maxn * 4], pre[maxn];

void update(int id, int l, int r, int from, int to, ll value) {
    if(r < from || l > to) return;
    if(from <= l && r <= to) {
        seg[id] = min(seg[id], value);
        return;
    }
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, from, to, value);
    update(id << 1 | 1, mid + 1, r, from, to, value);
    seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}

ll query(int id, int l, int r, int from, int to) {
    if(r < from || l > to) return 1e18;
    if(from <= l && r <= to) return seg[id];
    int mid = (l + r) >> 1;
    return min(query(id << 1, l, mid, from, to), query(id << 1 | 1, mid + 1, r, from, to));
}

void solve() {
    memset(pre, 0, sizeof(pre));
    cin >> n >> k;

    for(int i = 1; i <= k; i++) {
        int l, r; cin >> l >> r;
        ll c; cin >> c;
        adj[r].pb({l, c});
        pre[l]++, pre[r + 1]--;
    }

    for(int i = 1; i <= n; i++)
        pre[i] += pre[i - 1];
    for(int i = 1; i <= n; i++) 
        if(pre[i] == 0) {
            cout << "Impossible" << '\n';
            return;
        }
    
    memset(dp, 0x3f, sizeof(dp));
    memset(seg, 0x3f, sizeof(seg));
    dp[0] = 0;

    for(int i = 1; i <= n; i++) {
        for(pair<int, ll> tmp : adj[i]) {
            int l = tmp.fi, r = i, cost = tmp.se;
            dp[i] = min(dp[i], min(dp[l - 1], query(1, 1, n, l, r)) + cost);
            update(1, 1, n, i, i, dp[i]);
        }
    }

    cout << dp[n] << '\n';
}

int main(){ 
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    bool ok = false;
    if(ok) {
        int t; cin >> t;
        while(t--)  solve();
    }   
    else
        solve();
}

:::

------

## D. Đấu giá nhà

:::spoiler Tóm tắt đề
>Ta được cho một đồ thị dạng cây, trong đó đỉnh $i$ ban đầu có giá trị là $c_i$
>Được cho thêm $p$ truy vấn thuộc dạng $u, v, w$, yêu cầu ta phải maximize giá trị của các đỉnh trên đường đi $u - v$ với $w$
>Cuối cùng là phải trả lời $q$ truy vấn thuộc dạng $u, v$, nghĩa là ta cần biết tổng giá trị các đỉnh trên đường đi $u - v$
:::

### Sub 1

:::spoiler Editorial
:::info
>$n, p, q \leq 1000$
>
>Vì $n, p, q$ bé nên ta hoàn toàn có thể xử lí cả 2 loại truy vấn bằng dfs cơ bản.
>
>Với mỗi lần dfs sẽ có đpt tệ nhất là $O(n)$
>
>Đpt cuối cùng sẽ là: $O((p + q) * n)$

:::

:::spoiler Solution

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

const int maxn = 5e5 + 55;
vector<int> adj[maxn];
long long cost[maxn], finalCost[maxn], depW[maxn];
 
vector<int> path;
void dfs(int u, int p, int des, long long w) {
    path.push_back(u);
    if (u == des) {
        for (int v : path)
            finalCost[v] = max(finalCost[v], w);
    }
    else {
        for (int v : adj[u]) {
            if (v == p) continue;
            
            dfs(v, u, des, w);
        }
    }

    path.pop_back();
}

long long res = 0;
void dfs2(int u, int p, int des) {
    path.push_back(u);
    if (u == des) {
        for (int v : path)
            res += cost[v];
    }
    else {
        for (int v : adj[u]) {
            if (v == p) continue;
            
            dfs2(v, u, des);
        }
    }

    path.pop_back();
}
 
int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n, p, q;
    cin >> n >> p >> q;
 
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
 
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
 
        adj[u].push_back(v), adj[v].push_back(u);
    }
    
    for (int i = 0; i < p; i++) {
        long long u, v, w;
        cin >> u >> v >> w;
        
        dfs(u, u, v, w);
    }
    
    for (int i = 1; i <= n; i++)
        cost[i] = max(cost[i], finalCost[i]);
        
    for (int i = 0; i < q; i++) {
        long long u, v;
        cin >> u >> v;
        
        res = 0;
        dfs2(u, u, v);
        cout << res << '\n';               
    }
}

:::

### Sub 2
:::spoiler Editorial
:::info
>Luôn có đường đi trực tiếp từ ngôi nhà $i$ tới $i + 1$
>
>Trong sub này cây sẽ là một đường thẳng, làm 2 loại truy vấn dễ xử lí hơn nhiều
>
>Bây giờ $p$ truy vấn đầu tiên trở thành: maximize một đoạn $[l, r]$ với giá trị $w$.
>Đây là một bài toán cổ điển và có thể được giải quyết bằng Segment tree + Lazy update trong $O(\log(n))$
>
>Sau khi xử lí xong $p$ truy vấn thì ta sẽ có giá trị cuối cùng của mỗi đỉnh, vì thế ta hoàn toàn có thể tạo mảng tổng tiền tố và trả lời $q$ truy vấn cuối cùng trong $O(1)$ với mỗi truy vấn
>
>Đpt cuối cùng sẽ là: $O((n + p)*log(n))$

:::

:::spoiler Solution

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

const int maxn = 5e5 + 55;
vector<int> adj[maxn];
long long cost[maxn], finalCost[maxn], depW[maxn];
long long pref[maxn], seg[maxn * 4], lazy[maxn * 4];

void Push(int v) {
    seg[v << 1] = max(seg[v << 1], lazy[v]);
    seg[v << 1 | 1] = max(seg[v << 1 | 1], lazy[v]);
    lazy[v << 1] = max(lazy[v << 1], lazy[v]);
    lazy[v << 1 | 1] = max(lazy[v << 1 | 1], lazy[v]);

    lazy[v] = 0;
}

void Update(int v, int tl, int tr, int l, int r, long long w) {
    if (tl == l && tr == r) {
        seg[v] = max(seg[v], w);
        lazy[v] = max(lazy[v], w);

        return;
    }

    int mid = (tl + tr) >> 1;

    Push(v);

    if (r <= mid) Update(v << 1, tl, mid, l, r, w);
    else if (l > mid) Update(v << 1 | 1, mid + 1, tr, l, r, w);
    else {
        Update(v << 1, tl, mid, l, mid, w);
        Update(v << 1 | 1, mid + 1, tr, mid + 1, r, w);
    }

    seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
}

long long Query(int v, int tl, int tr, int l, int r) {
    if (tl == l && tr == r)
        return seg[v];

    int mid = (tl + tr) >> 1;

    Push(v);

    if (r <= mid) return Query(v << 1, tl, mid, l, r);
    else return Query(v << 1 | 1, mid + 1, tr, l, r);
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, p, q;
    cin >> n >> p >> q;
 
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
 
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
 
        adj[u].push_back(v), adj[v].push_back(u);
    }
    
    for (int i = 0; i < p; i++) {
        long long u, v, w;
        cin >> u >> v >> w;
        
        if (u > v) swap(u, v);

        Update(1, 1, n, u, v, w);
    }
    
    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        cost[i] = max(cost[i], Query(1, 1, n, i, i));
        pref[i] = pref[i - 1] + cost[i];
    }

    for (int i = 0; i < q; i++) {
        long long u, v;
        cin >> u >> v;
        
        if (u > v) swap(u, v);

        cout << pref[v] - pref[u - 1] << '\n';           
    }
}

:::

### Sub 3
:::spoiler Editorial
:::info
>không có ràng buộc gì thêm
>
>Bài này có thể được giải bằng HLD trong $O(p * log(n)^{2})$, nhưng ta sẽ làm tốt hơn bằng DSU và LCA trong $O((n + p)*log(n))$
>
>Ta sẽ cho rằng các đỉnh ban đầu có giá trị là $0$, sau khi trải qua $p$ truy vấn thì ta sẽ maximize lại giá trị mọi đỉnh $i$ với $c_i$
>
>Ta nhận thấy rằng với mỗi truy vấn, ta phải update maximize đường đi $u-v$ trên cây với $w$, nhưng vì giá trị w không nhất thiết là lớn hơn giá trị nào trên đường đi $u-v$, nên có rất nhiều thời gian đang bị lãng phí
>Thay vào đó thì ta nghĩ ngay tới việc sort lại $p$ truy vấn theo $w$ giảm dần, từ đó ta thấy rằng những đường đi đã được update thì những đỉnh trên đường đi đó sẽ không bao giờ được update lại (vì $w_{i - 1} <= w_i$)
>
>Nhưng làm sao để update một đường đi $u-v$ nhanh ?. Ta sẽ dùng DSU, đặt rễ của cây là $1$, ban đầu đỉnh $i$ sẽ chỉ tới chính nó, sau khi đỉnh $i$ được update thì ta sẽ chỉ $i$ tới đỉnh cha của $i$ trên cây.
>Khi ta làm như vậy thì hàm tìm đỉnh đại diện thành phần liên thông của DSU (tạm gọi là root(u)) sẽ trả về **tổ tiên gần nhất** của $u$ mà chưa được update trước đây
>
>Khi đó mỗi đỉnh ta sẽ nối với đỉnh cha nó cùng lắm 1 lần, và tổng số lần nối là $n - 1$. Nếu ta dùng tối ưu nén đường đi của DSU thì ta sẽ có đpt cuối cùng là $O(\alpha * n)$
>
>Bây giờ để update một đường đi $u-v$ thì ta sẽ tìm LCA trong O(log(n)), và update từ $u$ và $v$ cho tới khi ta gặp một đỉnh có độ sâu < LCA (tức là không ở trên đường đi $u-v$)
>
>Với $q$ truy vấn cuối cùng thì ta đơn giản chỉ cần dfs lại một lần nữa, và tính tổng đường đi $u-v$ bằng LCA trong $O(log(n))$
>
>Từ đó ta có đpt cuối cùng là: $O((n + p) * log(n))$
:::

:::spoiler Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int LOG = 20;
const int maxn = 5e5 + 55;
vector<int> adj[maxn];
long long cost[maxn], finalCost[maxn], depW[maxn];
int jump[maxn][LOG + 1];
int par[maxn], dep[maxn];
 
int root(int u) {
    return (par[u] == u ? u : par[u] = root(par[u]));
}
 
int LCA(int u, int v) {
    if (dep[u] < dep[v])
        swap(u, v);
 
    for(int d = dep[u] - dep[v]; d > 0; d -= (d&-d))
        u = jump[u][__builtin_ctz(d)];
 
    if (u == v) return u;
 
    for (int j = LOG; j >= 0; j--) 
        if (jump[u][j] != jump[v][j])
            u = jump[u][j], v = jump[v][j];
 
    return jump[u][0];
}
 
void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    jump[u][0] = p;
 
    for (int v : adj[u]) {
        if (v == p) continue;
        
        dfs(v, u);
    }
}
 
void dfs2(int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
 
        depW[v] = depW[u] + cost[v];
        dfs2(v, u);
    }
}
 
void update(int u, int v, long long w) {
    int p = LCA(u, v);
    
    int cur = root(u);
    while (dep[cur] >= dep[p]) {
        finalCost[cur] = w;
        par[cur] = jump[cur][0];
        cur = root(cur);
    }
 
    cur = root(v);
    while (dep[cur] >= dep[p]) {
        finalCost[cur] = w;
        par[cur] = jump[cur][0];
        cur = root(cur);
    }
}
 
int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n, p, q;
    cin >> n >> p >> q;
 
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
 
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
 
        adj[u].push_back(v), adj[v].push_back(u);
    }
    
    dfs(1, 0);
    for (int j = 1; j <= LOG; j++)
        for (int i = 1; i <= n; i++)
            jump[i][j] = jump[jump[i][j - 1]][j - 1];
 
    vector<array<long long, 3>> ord(p);
    for (int i = 0; i < p; i++) {
        long long u, v, w;
        cin >> u >> v >> w;
 
        ord[i] = {w, u, v};
    }
    sort(ord.rbegin(), ord.rend());
 
    for (int i = 1; i <= n; i++)
        par[i] = i, finalCost[i] = 0;
    
    for (int i = 0; i < ord.size(); i++) 
        update(ord[i][1], ord[i][2], ord[i][0]);
 
    for (int i = 1; i <= n; i++)
        cost[i] = max(cost[i], finalCost[i]);
 
    depW[1] = cost[1];
    dfs2(1, 0);
    
    for (int i = 0; i < q; i++) {
        long long u, v;
        cin >> u >> v;
                    
        int p = LCA(u, v);
        cout << depW[u] + depW[v] - depW[p] * 2 + cost[p] << '\n'; 
    }
}

:::