本文共 3647 字，大约阅读时间需要 12 分钟。
给定一棵n个点的树，给定m个人的信息（m ≤ n），每个点可以有任意多个人的信息。然后给q个询问，每次询问u到v路径上的点上的编号最小的k（k ≤ 10）个人的数量。没有那么多人则输出0。
解法一：树上倍增法
观察到k的大小只有10，因此我们可以使用倍增的思想来处理前k小数的问题。在树结构中，我们可以预处理每个节点到根节点的路径信息，并将这些信息以倍增的方式存储。这样，在处理查询时，我们可以快速分解路径并收集前k小的编号。
具体步骤如下：
预处理每个节点的父节点和深度信息。 使用倍增法预处理每个节点到根节点的路径信息，存储前k小的编号。 对于每个查询，找到u和v的最低公共祖先（LCA），并分解路径为u到LCA和v到LCA两部分。 在每一部分中，收集前k小的编号，并进行合并，得到最终的k个最小编号。 这种方法的时间复杂度主要取决于倍增的层数和查询的路径长度。由于k较小，这种方法在时间和空间上都是高效的。
代码示例：
#include #define mid ((l + r) >> 1)#define Lson rt << 1, l, mid#define Rson rt << 1 | 1, mid + 1, r#define ms(a, al) memset(a, al, sizeof(a))#define log2(a) log(a) / log(2)#define _for(i, a, b) for (int i = (a); i < (b); ++i)#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)#define for_(i, a, b) for (int i = (a); i >= (b); --i)#define rep_(i, a, b) for (int i = (a); i > (b); --i)#define lowbit(x) ((-x) & x)#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)#define INF 0x3f3f3f3f#define LLF 0x3f3f3f3f3f3f3f3fusing namespace std;const int N = 4e5 + 10;const int maxn = 4e5 + 10;const long double eps = 1e-5;const int EPS = 500 * 500;typedef long long ll;typedef unsigned long long ull;typedef pair PII;typedef pair PLL;typedef pair PDD;const int BUF = 30000000;char Buf[BUF], *buf = Buf;template void read(T &a) { for (a = 0; *buf < 48; ++buf) ; while (*buf > 47) a = a * 10 + (*buf++) - 48;}template void read(T &first, Args &... args) { read(first); read(args...);}int n, m, q;vector G[N];vector > pre[N][30];int fa[N][20], depth[N];inline vector Merge(vector a, vector b) { vector ans; int poia = 0, poib = 0; while (ans.size() < 10 && poia < a.size() && poib < b.size()) { if (a[poia] < b[poib]) ans.push_back(a[poia ++]); else ans.push_back(b[poib ++]); } while (ans.size() < 10 && poia < a.size()) ans.push_back(a[poia ++]); while (ans.size() < 10 && poib < b.size()) ans.push_back(b[poib ++]); return ans;}inline void dfs(int u, int f) { fa[u][0] = f; for (int i = 1; i <= 17; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1]; for (int j = 1; j <= 17; ++j) { pre[u][j] = Merge(pre[u][j - 1], pre[fa[u][j - 1]][j - 1]); } depth[u] = depth[f] + 1; for (auto it : G[u]) { if (it == f) continue; dfs(it, u); }}inline int LCA(int u, int v) { if (depth[u] > depth[v]) swap(u, v); int delta = depth[v] - depth[u]; for (int i = 0; i <= 17; ++i) if (delta > i && 1) v = fa[v][i]; if (u == v) return v; for (int i = 17; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; return fa[u][0];}inline vector slove(int u, int v) { vector res; int delta = depth[u] - depth[v]; for (int j = 0; j <= 17 && u; ++j) if (delta > j && 1) res = Merge(res, pre[u][j]), u = fa[u][j]; return res;}int main() { read(Buf, 1, BUF, stdin); read(n, m, q); for (int i = 0; i < n - 1; ++i) { int l, r; read(l, r); G[l].push_back(r); G[r].push_back(l); } for (int i = 1; i <= m; ++i) { int x; read(x); pre[x][0].push_back(i); } for (int i = 1; i <= n; ++i) sort(pre[i][0].begin(), pre[i][0].end()); dfs(1, 0); while (q--) { int u, v, a; read(u, v, a); int lca = LCA(u, v); vector ans, res; ans = slove(u, lca); res = slove(v, lca); res = Merge(ans, res); res = Merge(res, pre[lca][0]); if (res.size() == 0) { puts("0"); continue; } int need = min(a, (int)res.size()); puts(""); for (int i = 0; i < need; ++i) { printf("%d", res[i]); if (i != need - 1) printf(" "); } } return 0;}
解法二：主席树
由于树上的信息具有可加性，我们可以使用主席树来处理路径上的信息。具体来说，我们将树分解为多个链，每个链内的信息可以独立处理。对于查询u到v的路径，我们可以分解为多个链进行处理，并对每个链内的信息进行合并，得到最终的k个最小编号。
这种方法的优势在于，主席树可以高效地处理路径上的信息，并且支持快速查询前k小的编号。预处理和查询的时间复杂度都较低，适合处理大规模数据。
总结
两种方法都可以有效地处理这个问题，但倍增法在实现上可能更为简单和高效，特别是考虑到k的限制使得预处理和查询的复杂度得以控制。
转载地址：http://fpvzz.baihongyu.com/