Tóm tắt lại đề:

• Một cây gồm ~n~ đỉnh. Mỗi đỉnh có giá trị ~c_i~.

• ~Q~ truy vấn. Mỗi truy vấn gồm tập ~s_t~ gồm một số đỉnh trong ~n~ đỉnh. In ra giá trị lớn nhất của tích số lượng điểm trên đường đi từ ~u~ tới ~v~ nhân min của các ~c_i~ trên đường đi ấy với ~u,v ∈ S~, tổng quát công thức (~dist(u,v) + 1) \cdot min(c_u, \ldots, c_v~) với ~u,v ∈ S~

ĐPT: ~O(T \cdot log^2 T)~ với ~T = 2 \cdot 10^5~.

Vì chỉ duy có 1 đường đi từ 2 buôn bất kì nên chứng minh được sơ đồ đường đi của thành phố có dạng hình cây.

Dựng virtual tree với mỗi truy vấn, có thể dựng các cạnh (thể hiện giá tiền nhỏ nhất trên đường đi) bằng lca + rmq. Tham lam với các cạnh ấy. Duyệt ngược tập cạnh giảm dần theo mức tiền, nếu xét tại đỉnh ta có trường hợp bắt đầu chính nó kết thúc tại chính nó, còn khi xây dựng một cạnh ta sẽ merge lại bằng dsu, cũng như tính toán khoảng cách xa nhất của ~2~ điểm trong tập hợp cạnh khi nối lại. Gọi khoảng cách xa nhất ấy là ~D~. Đáp án có thể là (~D+1 \cdot C~)

Tính toán đường kính. Nếu trong tập hợp ~S~ ta xác định được (~u_s, v_s~) là 2 đỉnh thuộc tập ~S~, khi thêm ~1~ đỉnh ~x~ bất kì vô tập hợp, đường kính mới lúc này có thể là (~u_s,x~), (~v_s,x~) hoặc vẫn là (~u_s, v_s~).

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

// Usage: RMQ<int, _min> rmq(a);

template<class T, T (*op) (T, T)> struct RMQ {
    RMQ() = default;
    RMQ(const vector<T>& v) : t{v}, n{(int) v.size()} {
        for (int k = 1; (1<<k) <= n; ++k) {
            t.emplace_back(n - (1<<k) + 1);
            for (int i = 0; i + (1<<k) <= n; ++i) {
                t[k][i] = op(t[k-1][i], t[k-1][i + (1<<(k-1))]);
            }
        }
    }
    // get range [l, r), doesn't work for empty range
    T get(int l, int r) const {
        assert(0 <= l && l < r && r <= n);
        int k = __lg(r - l);
        return op(t[k][l], t[k][r - (1<<k)]);
    }
private:
    vector<vector<T>> t;
    int n;
};
template<class T> T _min(T a, T b) { return b < a ? b : a; }
template<class T> T _max(T a, T b) { return a < b ? b : a; }

struct Tree {
    vector<int> depth, parent, siz, head, begin, end, inv_begin;
    RMQ<int, _min> rmq;
    Tree(const int &n, const vector<vector<int>> &adj, int root = 0) : depth(n), parent(n), siz(n), head(n), begin(n), end(n), inv_begin(n) {
        auto dfs = [&](auto self, int u, int p) -> void {
            depth[u] = p == -1 ? 0 : depth[p] + 1;
            parent[u] = p;
            siz[u] = 1;
            for (int v : adj[u]) {
                if (v == p) continue;
                self(self, v, u);
                siz[u] += siz[v];
            }
        };
        dfs(dfs, root, -1);
        int tim = 0;
        auto decompose = [&](auto self, int u, int h) -> void {
            head[u] = h;
            int heavy = -1;
            begin[u] = tim++;
            inv_begin[begin[u]] = u;
            for (int v : adj[u]) {
                if (v == parent[u]) continue;
                if (heavy == -1 || siz[v] > siz[heavy]) heavy = v;
            }
            if (heavy != -1) self(self, heavy, h);
            for (int v : adj[u]) {
                if (v == parent[u] || v == heavy) continue;
                self(self, v, v);
            }
            end[u] = tim;
        };
        decompose(decompose, root, root);
    }
    void setWeight(const vector<int> &a) {
        int n = a.size();
        vector <int> b(n);
        for (int i = 0; i < n; i++) b[getNode(i)] = a[i];
        rmq = RMQ<int, _min>(b);

    }
    int getDepth(int u) {
        return depth[u];
    }
    int getParent(int u) {
        return parent[u];
    }
    int getAncestor(int u, int k) { // returns the kth ancestor of u, -1 if out of tree. For example: 0th is u, 1st is parent(u),...
        while (k > 0 && u != -1) {
            if (k > depth[u] - depth[head[u]]) {
                k -= depth[u] - depth[head[u]] + 1;
                u = parent[head[u]];
            } else {
                u = inv_begin[begin[u] - k];
                k = 0;
            }
        }
        return u;
    }
    bool isDescendant(int upper, int lower) {
        return begin[upper] <= begin[lower] && begin[lower] < end[upper];
    }
    bool isProperDescendant(int upper, int lower) {
        return begin[upper] < begin[lower] && begin[lower] < end[upper];
    }
    int getLCA(int u, int v) {
        for (; head[u] != head[v]; v = parent[head[v]]) {
            if (depth[head[u]] > depth[head[v]]) swap(u, v);
        }
        if (depth[u] > depth[v]) swap(u, v);
        return u;
    }
    int getDist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[getLCA(u, v)];
    }
    int getMin(int u, int v) {
        int ans = 1e18;
        for (auto [l, r] : getPath(u, v))
            ans = min(ans, rmq.get(l, r));
        return ans;
    }
    int getIntermediate(int heavy, int u) { // returns the first node that isn't 'heavy' on the path from 'heavy' to 'u'
        assert(heavy != u);
        if (heavy != getLCA(u, heavy)) {
            return parent[heavy];
        }
        while (head[u] != head[heavy]) {
            u = head[u];
            if (parent[u] == heavy) return u;
            u = parent[u];
        }
        return inv_begin[begin[heavy] + 1];
    }
    int getNode(int u) { // maps nodes -> positions in the Euler tour
        return begin[u];
    }
    int getInvNode(int p) { // maps Euler tour positions -> nodes
        return inv_begin[p];
    }
    array<int, 2> getSubtree(int u) { // returns the subtree rooted at u, presented by the range of positions in the Euler tour
        return array<int, 2>{ begin[u], end[u] };
    }
    vector<array<int, 2>> getPath(int u, int v) { // returns the path [u, v], presented by a list of O(log) ranges that are the positions in the Euler tour
        vector<array<int, 2>> res;
        for (; head[u] != head[v]; v = parent[head[v]]) {
            if (depth[head[u]] > depth[head[v]]) swap(u, v);
            res.push_back({ begin[head[v]], begin[v] + 1 });
        }
        if (depth[u] > depth[v]) swap(u, v);
        res.push_back({ begin[u], begin[v] + 1 });
        return res;
    }
    pair<vector<int>, vector<array<int, 2>>> virtualTree(vector<int> nodes) { // returns a pair: the list of nodes in the virtual tree (at most 2*|nodes|), and the list of edges of that virtual tree
        sort(nodes.begin(), nodes.end(), [&](int u, int v) { return begin[u] < begin[v]; });
        int siz = nodes.size();
        for (int i = 0; i + 1 < siz; i++) {
            nodes.push_back(getLCA(nodes[i], nodes[i + 1]));
        }
        sort(nodes.begin(), nodes.end(), [&](int u, int v) { return begin[u] < begin[v]; });
        nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());
        vector<array<int, 2>> edges;
        vector<int> stk;
        for (int u : nodes) {
            while (!stk.empty() && !isProperDescendant(stk.back(), u)) {
                stk.pop_back();
            }
            if (!stk.empty()) {
                edges.push_back({stk.back(), u});
            }
            stk.push_back(u);
        }
        return {nodes, edges};
    }
};

signed main() {
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr); cout.tie(nullptr);

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

    int n, m, q; cin >> n >> m >> q;
     assert(m == n - 1);
    vector<int> a(n);
    vector <vector<int>> adj(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    Tree tree(n, adj);
    tree.setWeight(a);

    vector <int> p(n), s(n);
    vector <array<int, 2>> dia(n);
    for (int i = 0; i < n; i++) {
        p[i] = i;
        s[i] = 1;
        dia[i] = {i, i};
    }

    while (q--) {
        vector <int> S;
        {
            int k; cin >> k;
            while (k--) {
                int x; cin >> x; x--;
                S.push_back(x);
            }
        }
        sort(S.begin(), S.end());
        auto [nodes, edges] = tree.virtualTree(S);
        vector <array<int, 3>> w_edges;
        for (auto [u, v] : edges)
            w_edges.push_back({tree.getMin(u, v), u, v});
        sort(w_edges.begin(), w_edges.end(), greater<array<int, 3>>());


        int ans = 0;

        for (int i : nodes) {
            p[i] = i;
            s[i] = 1;
            if (binary_search(S.begin(), S.end(), i))
                dia[i] = {i, i},
                ans = max(ans, a[i]);
            else dia[i] = {-1, -1};
        }


        auto get = [&](auto self, int u) -> int {
            return p[u] == u ? u : p[u] = self(self, p[u]);
        };

        auto U = [&](int u, int v) -> array<int, 2> {
            u = get(get, u);
            v = get(get, v);
            if (u == v) return dia[u];
            if (s[u] > s[v]) swap(u, v);
            s[v] += s[u];
            p[u] = v;
            array<int, 3> ans;
            ans = {-1, -1, -1};
            for (int i = 0; i < 2; i++)
                for (int j = 0; j < 2; j++)
                    if (dia[u][i] != -1 && dia[v][j] != -1)
                    ans = max(ans, {tree.getDist(dia[u][i], dia[v][j]), dia[u][i], dia[v][j]});

            if (dia[u][0] != -1 && dia[u][1] != -1)
            ans = max(ans, {tree.getDist(dia[u][0], dia[u][1]), dia[u][0], dia[u][1]});

            if (dia[v][0] != -1 && dia[v][1] != -1)
            ans = max(ans, {tree.getDist(dia[v][0], dia[v][1]), dia[v][0], dia[v][1]});

            dia[v] = {ans[1], ans[2]};
            return dia[v];
        };

        for (auto [w, u, v] : w_edges) {
            auto [x, y] = U(u, v);
            if (x != -1 && y != -1)
                ans = max(ans, w * (tree.getDist(x, y) + 1));
        }

        cout << ans << '\n';


    }
}