题目分析这道题的核心是理解树的构造方式然后快速求两个结点的距离。树有 109109 个结点编号从 1 到 109109。根结点是 1。对于编号 k≥2k≥2它的父结点是 kk 的所有因数中除 kk 以外最大的那个因数。关键观察一个数 kk 的“除自身外最大的因数”就是 kk 除以它的最小质因子。举个例子1222×31222×3最小质因子是 2所以父结点是 12/2612/26。153×5153×5最小质因子是 3所以父结点是 15/3515/35。77 是质数最小质因子是 7所以父结点是 7/717/71。所以这棵树实际上就是每个结点不断除以自己的最小质因子直到变成 1这一条路径就是它到根结点的路径。求解思路两个结点 xx 和 yy 之间的距离就是 xx 到根的距离 yy 到根的距离 - 2 × 它们最近公共祖先LCA到根的距离。但这里我们不需要复杂的数据结构因为每个结点到根的路径长度最多是 log2(109)≈30log2(109)≈30因为每次至少除以 2。所以我们只需要找最小质因子预处理出 105105 以内的质数因为 109≈31623109≈31623筛到 105105 足够然后对每个数快速分解。求路径从 xx 开始不断除以它的最小质因子直到变成 1记录路径上的所有结点包括自己。找 LCA对 xx 和 yy 的路径从根结点 1 开始向下比较最后一个相同的结点就是 LCA。计算距离根据上面公式计算。复杂度预处理质数O(105loglog105)O(105loglog105)每组询问分解一个数O(logn)O(logn) 次除法每组询问求路径和 LCAO(logn)O(logn)总复杂度O(qlogn)O(qlogn)完全可过q≤1000q≤1000。参考代码#include bits/stdc.h using namespace std; const int MAXN 100000; vectorint primes; bool isPrime[MAXN 5]; // 欧拉筛预处理质数 void sieve() { memset(isPrime, true, sizeof(isPrime)); isPrime[0] isPrime[1] false; for (int i 2; i MAXN; i) { if (isPrime[i]) primes.push_back(i); for (int p : primes) { if (i * p MAXN) break; isPrime[i * p] false; if (i % p 0) break; } } } // 求 x 的最小质因子 int minPrimeFactor(int x) { for (int p : primes) { if (p * p x) break; if (x % p 0) return p; } return x; // x 本身是质数 } // 获取从 x 到根 1 的路径从 x 开始向上到 1 vectorint getPath(int x) { vectorint path; while (x 1) { path.push_back(x); int p minPrimeFactor(x); x / p; } path.push_back(1); reverse(path.begin(), path.end()); // 从根到 x 的顺序 return path; } int main() { ios::sync_with_stdio(false); cin.tie(0); sieve(); int q; cin q; while (q--) { int x, y; cin x y; vectorint px getPath(x); vectorint py getPath(y); // 找 LCA从根开始第一个不同的位置的前一个 int lca 1; int len min(px.size(), py.size()); for (int i 0; i len; i) { if (px[i] py[i]) lca px[i]; else break; } // 计算距离 int dist (px.size() - 1) (py.size() - 1) - 2 * (find(px.begin(), px.end(), lca) - px.begin()); cout dist \n; } return 0; }补充说明样例 2 中120的路径120 → 60 → 30 → 15 → 5 → 1长度 5650 2×5²×13的路径650 → 325 → 65 → 13 → 1长度 4。LCA 是 1距离 549549与输出一致。注意根结点 1 的特殊性1 没有父结点路径到 1 就停止。
GESP 202506 六级 - 树上距离
发布时间：2026/7/13 2:39:13
题目分析这道题的核心是理解树的构造方式然后快速求两个结点的距离。树有 109109 个结点编号从 1 到 109109。根结点是 1。对于编号 k≥2k≥2它的父结点是 kk 的所有因数中除 kk 以外最大的那个因数。关键观察一个数 kk 的“除自身外最大的因数”就是 kk 除以它的最小质因子。举个例子1222×31222×3最小质因子是 2所以父结点是 12/2612/26。153×5153×5最小质因子是 3所以父结点是 15/3515/35。77 是质数最小质因子是 7所以父结点是 7/717/71。所以这棵树实际上就是每个结点不断除以自己的最小质因子直到变成 1这一条路径就是它到根结点的路径。求解思路两个结点 xx 和 yy 之间的距离就是 xx 到根的距离 yy 到根的距离 - 2 × 它们最近公共祖先LCA到根的距离。但这里我们不需要复杂的数据结构因为每个结点到根的路径长度最多是 log2(109)≈30log2(109)≈30因为每次至少除以 2。所以我们只需要找最小质因子预处理出 105105 以内的质数因为 109≈31623109≈31623筛到 105105 足够然后对每个数快速分解。求路径从 xx 开始不断除以它的最小质因子直到变成 1记录路径上的所有结点包括自己。找 LCA对 xx 和 yy 的路径从根结点 1 开始向下比较最后一个相同的结点就是 LCA。计算距离根据上面公式计算。复杂度预处理质数O(105loglog105)O(105loglog105)每组询问分解一个数O(logn)O(logn) 次除法每组询问求路径和 LCAO(logn)O(logn)总复杂度O(qlogn)O(qlogn)完全可过q≤1000q≤1000。参考代码#include bits/stdc.h using namespace std; const int MAXN 100000; vectorint primes; bool isPrime[MAXN 5]; // 欧拉筛预处理质数 void sieve() { memset(isPrime, true, sizeof(isPrime)); isPrime[0] isPrime[1] false; for (int i 2; i MAXN; i) { if (isPrime[i]) primes.push_back(i); for (int p : primes) { if (i * p MAXN) break; isPrime[i * p] false; if (i % p 0) break; } } } // 求 x 的最小质因子 int minPrimeFactor(int x) { for (int p : primes) { if (p * p x) break; if (x % p 0) return p; } return x; // x 本身是质数 } // 获取从 x 到根 1 的路径从 x 开始向上到 1 vectorint getPath(int x) { vectorint path; while (x 1) { path.push_back(x); int p minPrimeFactor(x); x / p; } path.push_back(1); reverse(path.begin(), path.end()); // 从根到 x 的顺序 return path; } int main() { ios::sync_with_stdio(false); cin.tie(0); sieve(); int q; cin q; while (q--) { int x, y; cin x y; vectorint px getPath(x); vectorint py getPath(y); // 找 LCA从根开始第一个不同的位置的前一个 int lca 1; int len min(px.size(), py.size()); for (int i 0; i len; i) { if (px[i] py[i]) lca px[i]; else break; } // 计算距离 int dist (px.size() - 1) (py.size() - 1) - 2 * (find(px.begin(), px.end(), lca) - px.begin()); cout dist \n; } return 0; }补充说明样例 2 中120的路径120 → 60 → 30 → 15 → 5 → 1长度 5650 2×5²×13的路径650 → 325 → 65 → 13 → 1长度 4。LCA 是 1距离 549549与输出一致。注意根结点 1 的特殊性1 没有父结点路径到 1 就停止。
