Nhận xét rằng với mỗi truy vấn, đường kính của cây có thể thay đổi như sau:

• Đường kính của cây giữ nguyên so với cây ban đầu.
• Đường kính của cây là một đường đi đi qua đỉnh ~X_i~.

Trường hợp 1 có thể giải quyết bằng DP trên cây cơ bản, vì vậy, ta sẽ chỉ xét trường hợp thứ 2.

Nhận thấy rằng, một đường đi qua ~X_i~ có thể được tách thành 2 đường đi không giao cạnh xuất phát từ ~X_i~.

Nhận thấy rằng đường đi này có thể được biểu diễn dưới dạng:

~ K_i \cdot W + C ~

với ~W~ là trọng số của cạnh có chứa đỉnh ~X_i~, và ~C~ là đường đi dài nhất từ đỉnh kề với ~X_i~ và không đi qua ~X_i~.

Bài toán trở thành: Với mỗi truy vấn, tìm tổng của hai giá trị ~K_i \cdot W + C~ lớn nhất. Ta có thể giải quyết bài toán này bằng cách duy trì 2 convex hull cho mỗi đỉnh và chặt nhị phân với mỗi truy vấn.

Bài toán này cũng có thể được cài đặt bằng Lichao Tree hoặc Kinetic Tournament.

Độ phức tạp:

~ O((N + Q) \cdot \log_2 N) ~

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>

using namespace std;
const int N = 1e5 + 5, MOD = 1e9 + 7;  

struct Edge{
    int v, w;
};

vector<Edge> adj[N];
vector<pii> qq[N];

int n, q, ans[N];
pii dp[2][N];

int orig_diam = 0;

void dfs1(int i, int pre){
    dp[0][i] = dp[1][i] = {0, i};
    for(Edge e : adj[i]){
        if(e.v == pre) continue;
        dfs1(e.v, i);
        pii mx = dp[0][e.v]; mx.first += e.w, mx.second = e.v;
        if(mx > dp[0][i]){
            dp[1][i] = dp[0][i], dp[0][i] = mx;
        } else{
            dp[1][i] = max(dp[1][i], mx);
        }
    }
}

void dfs2(int i, int pre){
    orig_diam = max(orig_diam, dp[0][i].first + dp[1][i].first);
    for(Edge e : adj[i]){
        if(e.v == pre) continue;
        pii push = (dp[0][i].second == e.v ? dp[1][i] : dp[0][i]); push.first += e.w, push.second = i;
        if(push > dp[0][e.v]){
            dp[1][e.v] = dp[0][e.v], dp[0][e.v] = push;
        } else{
            dp[1][e.v] = max(dp[1][e.v], push);
        }
        dfs2(e.v, i);
    }
}

struct line{
    int a, b;

    inline int f(int x){
        return a * x + b;
    }

    bool useless(const line &nxt, const line &pre){
        double it1 = (b - pre.b) / (pre.a - a);
        double it2 = (b - nxt.b) / (nxt.a - a);
        return 1.0 * (b - nxt.b) * (pre.a - a) >= 1.0 * (b - pre.b) * (nxt.a - a);
    }
};
struct CHT{
    vector<line> h;
    vector<int> v;

    void add(const line &a, int id, vector<bool> &mark){
        while(h.size() > 1 && h.back().useless(a, h[h.size() - 2])){
            h.pop_back();
            mark[v.back()] = true;
            v.pop_back();
        }
        h.push_back(a);
        v.push_back(id);
    }

    pii bs(int l, int r, int x){
        int mid = (l + r) / 2;
        if(mid + 1 < h.size() && h[mid + 1].f(x) > h[mid].f(x)) return bs(mid + 1, r, x);
        if(mid - 1 >= 0 && h[mid - 1].f(x) > h[mid].f(x)) return bs(l, mid - 1, x);
        return {h[mid].f(x), mid};
    }   
};

void solve(){
    for(int i = 1; i <= n; i++){
        vector<line> f; 
        for(Edge e : adj[i]){
            pii opt = (dp[0][e.v].second == i ? dp[1][e.v] : dp[0][e.v]);
            f.push_back({e.w, opt.first});
        }
        sort(f.begin(), f.end(), [](const line &x, const line &y){return x.a < y.a || x.a == y.a && x.b < y.b;});
        vector<bool> mark(f.size());
        vector<int> ca;
        for(int i = 0; i < f.size(); i++){
            while(ca.size() && f[ca.back()].a == f[i].a) mark[ca.back()] = true, ca.pop_back();
            ca.push_back(i);
        }
        CHT hull1, hull2;
        for(int id : ca){
            hull1.add(f[id], id, mark);
        }
        ca.clear();
        for(int i = 0; i < f.size(); i++){
            if(!mark[i]) continue;
            while(ca.size() && f[ca.back()].a == f[i].a) mark[ca.back()] = true, ca.pop_back();
            ca.push_back(i);
        }
        for(int id : ca){
            hull2.add(f[id], id, mark);
        }
        for(pii q : qq[i]){
            int x = q.first;

            pii r1 = hull1.bs(0, hull1.h.size() - 1, x);
            int v1 = r1.first;
            int v2 = (hull2.h.size() ? hull2.bs(0, hull2.h.size() - 1, x).first : 0);
            if(r1.second) v2 = max(v2, hull1.h[r1.second - 1].f(x));
            if(r1.second + 1 < hull1.h.size()) v2 = max(v2, hull1.h[r1.second + 1].f(x));
            ans[q.second] = max({orig_diam, v1 + v2});
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }    
    cin >> q;
    for(int i = 1; i <= q; i++){
        int x, k; cin >> x >> k;
        qq[x].push_back({k, i});
    }
    dfs1(1, 1), dfs2(1, 1);
    solve();
    for(int i = 1; i <= q; i++){
        cout << ans[i] << "\n";
    }
}