【题目描述】：
最近有一场战争发生，Duff是战争里一名士兵，Malek是她的长官。
他们的国家——Andarz Gu有n个城市（编号为1到n），总共有n-1条道路，每条道路连接着不同的两个城市，保证两两城市间必定可以通过道路到达。
Andarz Gu总共有m个人，每个人分别对应着编号1到m，对于第i个人，我们可以知道他还有一个编号ci，表示这个编号为i的人住在编号为ci的城市。注意一个城市里可能有不止一个人，也可能没有人住在这个城市。
Malek喜欢下达指令，这也是她要问DuffQ（Q个问题，不是DuffQ 个问题）个问题的原因。每一个询问包含三个数u，v，a，Malek要问你的问题就是u到v最短的那条路径上前a小的人的编号分别是什么，如果路径上的人小于a个，就有多少个就输出多少个，如果一个也没有，直接输出0。
但是Duff现在十分的忙，所以她来向你寻求帮助，请你帮助她回答这q个询问。
【输入描述】：
第一行输入n，m，q（1<=n,m,q<=10^5）
接下来n-1行，一行输入两个数v和u，表示城市v和城市u之间有一条双向道路。
再接下来一行输入m个数，对于ci表示编号为i的人居住的城市。（1<=ci<=n）
再再接下来q行，每行三个数u,v,a表示一组询问（1<=v,u<=n;1<=a<=10）
【输出描述】：
对于每组询问，输出它要的答案。
【样例输入】：
5 4 5
1 3
1 2
1 4
4 5
2 1 4 3
4 5 6
1 5 2
5 5 10
2 3 3
5 3 1
【样例输出】：
1 3
2 2 3
0
3 1 2 4
1 2
#include<iostream>
#include<cstdio>
using namespace std;
struct data{
int x,y;
}t[200001];
struct node{
int p[11],cnt,fa;
}f[100001][21],ans;
int n,m,q,x,y,c,k[100001],d[100001],h[100001],fa;
void add(int a,int b,int id){
t[id].x=b;
t[id].y=h[a];
h[a]=id;
}
node ins(node a,node b){
node g;
int l=1,r=1;
g.cnt=0;
g.fa=b.fa;
while(l<=a.cnt||r<=b.cnt){
if(g.cnt==10)break;
if(l>a.cnt){
g.cnt++;
g.p[g.cnt]=b.p[r];
r++;
}else if(r>b.cnt){
g.cnt++;
g.p[g.cnt]=a.p[l];
l++;
}else if(a.p[l]<b.p[r]){
g.cnt++;
g.p[g.cnt]=a.p[l];
l++;
}else{
g.cnt++;
g.p[g.cnt]=b.p[r];
r++;
}
}
return g;
}
void dfs(int a){
for(int i=1;i<=20;i++)f[a][i]=ins(f[a][i-1],f[f[a][i-1].fa][i-1]);
for(int i=h[a];i;i=t[i].y){
if(!d[t[i].x]){
d[t[i].x]=d[a]+1;
f[t[i].x][0].fa=a;
dfs(t[i].x);
}
}
}
void lca(int a,int b){
if(d[a]>d[b]){
for(int i=20;i>=0;i--){
if(d[f[a][i].fa]>=d[b]){
ans=ins(ans,f[a][i]);
a=f[a][i].fa;
}
}
}
if(d[a]<d[b]){
for(int i=20;i>=0;i--){
if(d[f[b][i].fa]>=d[a]){
ans=ins(ans,f[b][i]);
b=f[b][i].fa;
}
}
}
for(int i=20;i>=0;i--){
if(f[b][i].fa!=f[a][i].fa){
ans=ins(ans,f[b][i]);
ans=ins(ans,f[a][i]);
b=f[b][i].fa;
a=f[a][i].fa;
}
}
if(a!=b){
ans=ins(ans,f[b][0]);
ans=ins(ans,f[a][0]);
a=f[a][0].fa;
}
ans=ins(ans,f[a][0]);
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y,i*2);
add(y,x,i*2+1);
}
for(int i=1;i<=m;i++){
scanf("%d",&x);
if(f[x][0].cnt<10){
f[x][0].cnt++;
f[x][0].p[f[x][0].cnt]=i;
}
}
d[1]=1;
dfs(1);
for(int i=1;i<=q;i++){
scanf("%d%d%d",&x,&y,&c);
ans.cnt=0;
lca(x,y);
ans.cnt=min(ans.cnt,c);
printf("%d ",ans.cnt);
for(int j=1;j<=ans.cnt;j++)printf("%d ",ans.p[j]);
printf("\n");
}
}
xsy 2414【CF587C】Duff in the Army
原文：https://www.cnblogs.com/ez-syh/p/11615466.html