题意概述：
给出一棵N个结点的树，然后有M个居民分散在这棵树的结点上（允许某个结点没有居民）。现在给出一些询问形如u,v,a，定义k=min(x,a)，其中x表示的是u->v路径上的居民数量。将所有路径上的居民编号升序排列之后得到序列p1,p2,...,px，要求对于每一组询问，输出k,p1,p2,...,pk。
N,M,Q<=10^5,1<=a<=10.
分析：
实际上这个题是被丢在数据结构作业里面的只是。。。。好像没有这个必要？
分析一波可以发现每个点可能在答案中出现的居民最多只有10个，所以说按照出现的顺序依次把每个点的至多10个居民储存起来，然后倍增的时候用归并排序的思想合并就可以了。时间复杂度O(10nlogn)。
实现过程中注意到一些问题，今后用倍增统计点的信息的时候都用半开半闭就好了，加上对链顶端（x=y时对x，否则x,y一起爬之后对x,y,fa[x][0]）的特判就可以做到不重不漏统计（之前都是用来求最值之类的所以没有注意到这个问题）。
所以。。。数据结构是树的意思吗。。。。（感觉听了小火车讲课之后写代码的时候都在各种压长度？）
所以这个时限的4s是输入输出的锅？（实测手写0.5s的事情）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
const int maxn=; int N,M,Q;
struct edge{ int to,next; }E[maxn<<];
int first[maxn],np,dep[maxn],fa[maxn][],info[maxn][][],sz[maxn][];
int ans[],tmp[]; void add_edge(int u,int v)
{
E[++np]=(edge){v,first[u]};
first[u]=np;
}
void data_in()
{
scanf("%d%d%d",&N,&M,&Q);
int x,y;
for(int i=;i<N;i++){
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
for(int i=;i<=M;i++){
scanf("%d",&x);
if(sz[x][]<) info[x][][sz[x][]++]=i;
}
}
int merge(int *a,int *b,int l1,int l2,int *c)
{
int l=,i=,j=;
while(i<l1&&j<l2&&l<) c[l++]=a[i]<b[j]?a[i++]:b[j++];
while(i<l1&&l<) c[l++]=a[i++];
while(j<l2&&l<) c[l++]=b[j++];
return l;
}
void DFS(int i,int f,int d)
{
fa[i][]=f,dep[i]=d;
for(int j=;(<<j)<d;j++){
fa[i][j]=fa[fa[i][j-]][j-];
sz[i][j]=merge(info[i][j-],info[fa[i][j-]][j-],sz[i][j-],sz[fa[i][j-]][j-],info[i][j]);
}
for(int p=first[i];p;p=E[p].next){
int j=E[p].to;
if(j==f) continue;
DFS(j,i,d+);
}
}
void cc(int *n,int &l,int x,int i)
{
l=merge(n,info[x][i],l,sz[x][i],tmp);
for(int k=;k<l;k++) n[k]=tmp[k];
}
void LCA(int x,int y,int *n,int &l)
{
if(dep[x]<dep[y]) swap(x,y);
int len=dep[x]-dep[y]; l=;
for(int i=;(<<i)<=len;i++)
if((<<i)&len){ cc(n,l,x,i); x=fa[x][i]; }
if(x==y){ cc(n,l,x,); return; }
for(int i=;i>=;i--) if(fa[x][i]!=fa[y][i]){
cc(n,l,x,i); cc(n,l,y,i);
x=fa[x][i],y=fa[y][i];
}
cc(n,l,x,); cc(n,l,y,);
cc(n,l,fa[x][],);
}
void work()
{
DFS(,,);
int x,y,a,l;
for(int i=;i<=Q;i++){
scanf("%d%d%d",&x,&y,&a);
LCA(x,y,ans,l);
printf("%d ",min(a,l));
for(int j=;j<min(a,l);j++) printf("%d ",ans[j]);
printf("\n");
}
}
int main()
{
data_in();
work();
return ;
96 }