题意：一个n个点的数， m个人住在其中的某些点上， 每个人的标号1-m， 询问u-v 路径上标号前a个人，并输出标号，a < 10。
作法， 利用倍增， ID[j][i] 表示i到i的第2^j个祖先上前10个人， 那么每次询问直接维护就好了，细节好多， 刚开始不知道怎么求ID[j][i]。
这里把2^j分成两部分， 前2^(j-1)和 后2^(j-1)个, 然后递推的维护。
感觉树链剖分也可以做， 不知道会不会TLE， 树链剖分的话 线段树的每个点维护10个值， 每次合并就行了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + ;
const int maxdep = ;
int par[maxdep][maxn], dep[maxn], n;
vector <int> ID[maxdep][maxn], cit[maxn];
vector <int> G[maxn];
void init() {
for (int i = ; i < maxn; i++) {
G[i].clear();
cit[i].clear();
for (int j = ; j < maxdep; j++) {
ID[j][i].clear();
}
}
memset(par, -, sizeof (par));
}
void update(vector <int> &v1, vector <int> &v2) {
for (int x: v2) {
v1.push_back(x);
}
sort (v1.begin(), v1.end());
v1.erase(unique(v1.begin(), v1.end()), v1.end());
while (v1.size() > ) {
v1.pop_back();
}
}
void dfs(int u, int father) {
par[][u] = father;
dep[u] = dep[father] + ;
for (int i = u; i <= u; i++) {
update(ID[][i], cit[par[][i]]);
update(ID[][i], cit[i]);
for (int j = ; j + < maxdep; j++) {
if (~par[j][i]) {
par[j+][i] = par[j][par[j][i]];
update(ID[j+][i], cit[i]);
update(ID[j+][i], ID[j][i]);
update(ID[j+][i], ID[j][par[j][i]]);
} else {
par[j+][i] = -;
}
}
}
for (int v: G[u]) {
if (v != father) {
dfs(v, u);
}
} }
int lca(int u, int v) {
if (dep[u] > dep[v]) {
swap(u, v);
}
for (int k = ; k < maxdep; k++) {
if ((dep[v] - dep[u]) >> k & ) {
v = par[k][v];
}
}
if (u == v) {
return u;
}
for (int i = maxdep-; i >= ; i--) {
if (par[i][u] != par[i][v]) {
u = par[i][u];
v = par[i][v];
}
}
return par[][u];
}
int anc;
vector <int> solve(int u, int v) {
vector <int> res;
if (u == v) {
update(res, cit[u]);
}
for (int i = maxdep-; i >= ; i--) {
if (~par[i][u] && dep[par[i][u]] >= dep[anc]) {
update(res, ID[i][u]);
u = par[i][u];
}
}
for (int i = maxdep-; i >= ; i--) {
if (~par[i][v] && dep[par[i][v]] >= dep[anc]) {
update(res, ID[i][v]);
v = par[i][v];
}
}
vector<int> emp;
update(res, emp);
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int m, q;
while (~scanf ("%d%d%d", &n, &m, &q)) {
init();
for (int i = ; i < n-; i++) {
int u, v;
scanf ("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = ; i < m; i++) {
int c;
scanf ("%d", &c);
if (cit[c].size() < ) {
cit[c].push_back(i+);
ID[][c].push_back(i+);
}
}
dfs(, );
while(q--) {
int u, v, a;
scanf ("%d%d%d", &u, &v, &a);
anc = lca(u, v);
auto res = solve(u, v);
int tot = min((int)res.size(), a);
printf("%d%c", tot, " \n"[!tot]);
for (int i = ; i < min((int)res.size(), a); i++) {
printf("%d%c", res[i], " \n"[i+==min((int)res.size(), a)]);
}
}
}
return ;
}