CF587C AC

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

class LPQ
{
  public:
    LPQ(int n) : n_(n) { data = vi(12, INT_MAX); }
    // LPQ(int n) : n_(n) {}
    void insert(int x)
    {
        /*
        data.insert(x);
        while (data.size() > 11) {
            data.erase(data.begin());
        }
        */
        for (int i = 0; i < 11; ++i)
            if (data[i] == x)
                return;
        data[11] = x;
        sort(data.begin(), data.end());
    }
    int n_;
    // priority_queue<int> data;
    // set<int, greater<int>> data;
    vi data;
};

int main(int argc, char **argv)
{
    // cin.tie(nullptr)->sync_with_stdio(false);
    // cout.tie(nullptr)->sync_with_stdio(false);
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, q, u, v, a;
    cin >> n >> m >> q;
    vector<vi> g(n + 1);
    for (int i = 1; i < n; ++i)
        cin >> u >> v, g[u].push_back(v), g[v].push_back(u);

    map<int, vector<int>> cs;
    for (int i = 0; i < m; ++i) {
        cin >> a;
        cs[a].push_back(i + 1);
    }
    for (auto &[k, v] : cs) {
        sort(v.begin(), v.end());
        if (v.size() > 10)
            v.erase(v.begin() + 10, v.end());
    }

    using a10i = array<int, 10>;
    constexpr int log = 18;
    vector<vi> pa(n + 1, vi(log));
    vector<vector<a10i>> ppl(n + 1, vector<a10i>(log));
    vi dep(n + 1);
    function<void(int, int, int)> dfs = [&](int u, int fa, int depth) {
        dep[u] = depth;
        if (fa != -1)
            pa[u][0] = fa;
        size_t pcnt = min(size_t(10), cs[u].size());
        for (int i = 0; i < pcnt; ++i)
            ppl[u][0][i] = cs[u][i];
        for (int i = 1; i < log; ++i) {
            pa[u][i] = pa[pa[u][i - 1]][i - 1];
            /*
            vi ss(ppl[u][i - 1].begin(), ppl[u][i - 1].end());
            ss.reserve(32);
            for (auto x : ppl[pa[u][i - 1]][i - 1])
                ss.push_back(x);
            set<int> ps(ss.begin(), ss.end());
            ps.insert(0);
            auto it = next(ps.begin());
            for (int j = 0; j < 10 && it != ps.end(); ++j, ++it) {
                ppl[u][i][j] = *it;
            }
            */
            const auto &pu = ppl[u][i - 1], &pv = ppl[pa[u][i - 1]][i - 1];
            int m = 0, n = 0, k = 0;
            while (k < 10 && m < 10 && n < 10 && pu[m] && pv[n]) {
                if (pu[m] < pv[n]) {
                    ppl[u][i][k] = pu[m];
                    ++k, ++m;
                } else {
                    ppl[u][i][k] = pv[n];
                    ++k, ++n;
                }
            }
            while (k < 10 && m < 10 && pu[m]) {
                ppl[u][i][k] = pu[m];
                ++m, ++k;
            }
            while (k < 10 && n < 10 && pv[n]) {
                ppl[u][i][k] = pv[n];
                ++n, ++k;
            }
        }
        for (auto v : g[u]) {
            if (v == fa)
                continue;
            dfs(v, u, depth + 1);
        }
    };
    dfs(1, -1, 0);

    function<vector<int>(int, int, int)> lca = [&](int u, int v, int a) {
        ll cnt = 0;
        set<int> ans{0};
        // priority_queue<int> pq;
        LPQ pq(10);
        // dbg(u, v);
        if (dep[u] < dep[v])
            swap(u, v);
        for (int step = log - 1; step >= 0; --step) {
            if (dep[pa[u][step]] >= dep[v]) {
                for (auto x : ppl[u][step])
                    pq.insert(x);
                u = pa[u][step];
            }
            ++cnt;
        }
        if (u != v) {
            for (int step = log - 1; step >= 0; --step) {
                if (pa[u][step] != pa[v][step]) {
                    for (auto x : ppl[u][step])
                        pq.insert(x);
                    for (auto x : ppl[v][step])
                        pq.insert(x);
                    u = pa[u][step], v = pa[v][step];
                }
                ++cnt;
            }
            for (auto x : ppl[u][0])
                pq.insert(x);
            for (auto x : ppl[v][0])
                pq.insert(x);
            u = pa[u][0];
        }

        for (auto x : cs[u])
            pq.insert(x);
        /*
        while (pq.data.size())
            ans.insert(pq.data.top()), pq.data.pop();
        */
        assert(cnt < 20 * 2);
        for (auto x : pq.data)
            if (x != INT_MAX)
                ans.insert(x);
        vector<int> ret;
        auto it = next(ans.begin());
        for (int i = 0; i < a && it != ans.end(); ++it, ++i)
            ret.push_back(*it);
        // dbg(ans, u);
        return ret;
    };
    for (int i = 0; i < q; ++i) {
        cin >> u >> v >> a;
        auto ans = lca(u, v, a);
        cout << ans.size();
        for (auto x : ans)
            cout << ' ' << x;
        cout << '\n';
    }
    return 0;
};