本文共 4530 字，大约阅读时间需要 15 分钟。

前言

题意

\(n\) 个城市，构成一棵树。给定 \(m\) 个人生活在的城市，输入时的 \(A_i\) 表示编号为 \(i\) 的人居住的城市。 有 \(q\) 次询问，给定两个城市，求两个城市的路径中，编号前 \(a\) 小的人的编号并输出。

思路

树上倍增。

可以将 \(u\) 到 \(v\) 的路径分为三个部分：

1. 从 \(u\) 到 \(lca\) 但不包含 \(lca\)的路径。
2. 从 \(v\) 到 \(lca\) 但不包含 \(lca\)的路径。
3. \(lca\) 这个点。

所以先预处理出 \(dis[i][j][k]\) ： \(i\) 向上跳 \(2^j-1\) 部第 \(k\) 小的值。由于查询的 \(a\leq10\) ，所以预处理出前 \(10\) 小的即可。

预处理代码：

for(int i = 1; i <= n; i++)	for(int j = 1; j <= 10; j++) dis[i][0][j] = w[i][j];for(int j = 1; j <= 30; j++)	for(int i = 1; i <= n; i++) {		fa[i][j] = fa[fa[i][j - 1]][j - 1];		for(int k = 1; k <= 10; k++) dis[i][j][k] = dis[fa[i][j - 1]][j - 1][k];		for(int k = 1; k <= 10; k++) dis[i][j][k + 10] = dis[i][j - 1][k];		sort(dis[i][j] + 1, dis[i][j] + 1 + 20);	}

查询分三部分，其实也跟普通的树上求简单路径的距离差不多。

先求出 \(lca\) ，再用 \(u\) 和 \(v\) 倍增分别向上爬即可。记得最后在算上 \(lca\) 。

时间复杂度 \(O(30n\log n)\) ，\(30\) 是因为 \(10\times \log 10\approx30\)。

Code

#include 
   
    #include 
    
     #include 
     
      using namespace std;namespace Quick_Function {	template 
      
        void Read(Temp &x) {		x = 0; char ch = getchar(); bool op = 0;		while(ch < '0' || ch > '9') { if(ch == '-') op = 1; ch = getchar(); }		while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }		if(op) x = -x;	}	template 
       
         void Read(T &t, Args &... args) { Read(t); Read(args...); }	template 
        
          Temp Max(Temp x, Temp y) { return x > y ? x : y; } template 
         
           Temp Min(Temp x, Temp y) { return x < y ? x : y; } template 
          
            Temp Abs(Temp x) { return x < 0 ? (-x) : x; } template 
           
             void Swap(Temp &x, Temp &y) { x ^= y ^= x ^= y; }}using namespace Quick_Function;#define INF 0x3f3f3f3fconst int MAXN = 1e5 + 5;struct Edge { int Next, To; };Edge edge[MAXN << 1];int head[MAXN], edgetot = 1;void Addedge(int u, int v) { edge[++edgetot].Next = head[u], edge[edgetot].To = v, head[u] = edgetot; edge[++edgetot].Next = head[v], edge[edgetot].To = u, head[v] = edgetot;}int w[MAXN][21];int n, m, q, a;int dep[MAXN], fa[MAXN][31], dis[MAXN][31][21];int res1[21], res2[21];int Get_Lca(int x, int y) { if(dep[x] < dep[y]) Swap(x, y); for(int i = 30; i >= 0; i--) if(dep[x] - (1 << i) >= dep[y]) x = fa[x][i]; if(x == y) return x; for(int i = 30; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0];}void dfs(int u, int step) { dep[u] = step; for(int i = head[u]; i; i = edge[i].Next) { int v = edge[i].To; if(v != fa[u][0]) { fa[v][0] = u; dfs(v, step + 1); } }}void Upclimb1(int x, int y) { memset(res1, 0x3f, sizeof(res1)); for(int i = 30; i >= 0; i--) if(dep[x] - (1 << i) >= dep[y]) { for(int k = 1; k <= 10; k++) res1[k + 10] = dis[x][i][k]; sort(res1 + 1, res1 + 1 + 20); x = fa[x][i]; }}void Upclimb2(int x, int y) { memset(res2, 0x3f, sizeof(res2)); for(int i = 30; i >= 0; i--) if(dep[x] - (1 << i) >= dep[y]) { for(int k = 1; k <= 10; k++) res2[k + 10] = dis[x][i][k]; sort(res2 + 1, res2 + 1 + 20); x = fa[x][i]; }}void Query(int x, int y) { int ans = 0; int lca = Get_Lca(x, y); if(lca == x) { Upclimb1(y, x); for(int i = 1; i <= 10; i++) res1[i + 10] = w[x][i]; sort(res1 + 1, res1 + 1 + 20); for(int i = 1; i <= a; i++) if(res1[i] != INF) ans++; printf("%d ", ans); for(int i = 1; i <= a; i++) if(res1[i] != INF) printf("%d ", res1[i]); return; } if(lca == y) { Swap(x, y); Upclimb1(y, x); for(int i = 1; i <= 10; i++) res1[i + 10] = w[x][i]; sort(res1 + 1, res1 + 1 + 20); for(int i = 1; i <= a; i++) if(res1[i] != INF) ans++; printf("%d ", ans); for(int i = 1; i <= a; i++) if(res1[i] != INF) printf("%d ", res1[i]); return; } Upclimb1(x, lca); Upclimb2(y, lca); for(int i = 1; i <= 10; i++) res1[i + 10] = res2[i]; sort(res1 + 1, res1 + 1 + 20); for(int i = 1; i <= 10; i++) res1[i + 10] = w[lca][i]; sort(res1 + 1, res1 + 1 + 20); for(int i = 1; i <= a; i++) if(res1[i] != INF) ans++; printf("%d ", ans); for(int i = 1; i <= a; i++) if(res1[i] != INF) printf("%d ", res1[i]);}int main() { memset(w, 0x3f, sizeof(w)); memset(dis, 0x3f, sizeof(dis)); Read(n, m, q); for(int i = 1, u, v; i < n; i++) Read(u, v), Addedge(u, v); for(int i = 1, a; i <= m; i++) { Read(a); w[a][11] = i; sort(w[a] + 1, w[a] + 1 + 11); } dfs(1, 0); for(int i = 1; i <= n; i++) for(int j = 1; j <= 10; j++) dis[i][0][j] = w[i][j]; for(int j = 1; j <= 30; j++) for(int i = 1; i <= n; i++) { fa[i][j] = fa[fa[i][j - 1]][j - 1]; for(int k = 1; k <= 10; k++) dis[i][j][k] = dis[fa[i][j - 1]][j - 1][k]; for(int k = 1; k <= 10; k++) dis[i][j][k + 10] = dis[i][j - 1][k]; sort(dis[i][j] + 1, dis[i][j] + 1 + 20); } int u, v; while(q--) { Read(u, v, a); Query(u, v); printf("\n"); } return 0;}