Ta có chi phí để di chuyển từ thành phố ~u~ đến thành phố ~v~ là tổng số lượng con đường và độ dài của chúng trên đường đi ngắn nhất từ ~u~ đến ~v~. Ta sẽ cộng độ dài của mỗi con đường tăng lên 1. Khi đó chi phí chính là tổng độ dài của các con đường từ ~u~ đến ~v~.

Vì đồ thị đã cho là một cây. Ta có thể sử dụng thuật toán đường kính để xử lí các truy vấn. Xét truy vấn có ~k_i~ đỉnh ~u_1, u_2, …, u_{k, i}~. Đầu tiên ta sẽ tìm đỉnh xa đỉnh ~1~ nhất trong ~k_i~ đỉnh trên, gọi đỉnh đó là ~U~. Sau đó ta sẽ tìm đỉnh xa đỉnh ~U~ nhất trên ~k_i~ đỉnh trên, gọi là ~V~. Độ dài của đường đi ~U~ đến ~V~ chính là đáp án của truy vấn.

Gọi ~dist_u~ là tổng độ dài đường đi từ ~1~ đến ~u~. Khi đó, để tìm đỉnh ~U~ xa đỉnh ~1~ nhất ta chỉ cần xét ~dist_{u_1}, dist_{u_2}, ..., dist_{u_{k_i}}~ trong ~O(k_i)~. Sau đó dùng công thức độ dài đường đi ~U~ đến ~V~ để tính đáp án trong ~O(k_i \times log_2(n))~ hoặc ~O(k_i)~ (tuỳ vào truy vấn tìm ~LCA~.

Vì ~\sum_{i=1}^{q} k_i \le n~ nên thuật toán có độ phức tạp là ~O(n \times log_2(n))~

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)1e6+228;
const int logn = 21;

int n, q, p = 0;
int FAI[N], h[N], minNode[N*2][logn+1];
vector<pii> adj[N];
long long dist[N];
#define MIN_HEIGHT(x,y) (h[x] < h[y] ? (x) : (y))

void dfs(int u, int par)
{
    minNode[++p][0] = u;
    FAI[u] = p;
    for(int i=0; i<(int)adj[u].size(); ++i)
    {
        int v = adj[u][i].fi, w = adj[u][i].se;
        if(v == par) continue;
        h[v] = h[u] + 1;
        dist[v] = dist[u] + w;
        dfs(v, u);
        minNode[++p][0] = u;
    }
}

int lca(int u, int v)
{
    int l = FAI[u], r = FAI[v];
    if(l > r) swap(l, r);
    int k = log2(r-l+1);
    return MIN_HEIGHT(minNode[l][k], minNode[r-MASK(k)+1][k]);
}

bool cmp(int x, int y)
{
    return dist[x] > dist[y];
}

void solve()
{
    cin >> n >> q;
    for(int i=1; i<n; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        ++w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }


    h[1] = 1;
    dfs(1, -1);

    for(int j=1; MASK(j) <= p; ++j)
    {
        for(int i=1; i+MASK(j)-1 <= p; ++i)
        {
            minNode[i][j] = MIN_HEIGHT(minNode[i][j-1], minNode[i+MASK(j-1)][j-1]);
        }
    }

    while(q--)
    {
        int k;
        cin >> k;
        vector<int> nodes;
        for(int i=0; i<k; ++i) 
        {
            int u; cin >> u;
            nodes.push_back(u);
        }
        sort(nodes.begin(), nodes.end(), cmp);
        long long res = 0;
        int u = nodes[0];
        for(int i=1; i<k; ++i)
        {
            int v = nodes[i];
            int w = lca(u, v);
            // cout << u << " " << v << " " << w << '\n';
            res = max(res, dist[u] + dist[v] - 2 * dist[w]);
        }
        cout << res << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   // freopen(task".inp" , "r" , stdin);
   // freopen(task".out" , "w" , stdout);
    solve();
    return 0;
}