输入格式第一行包含三个正整数 ,,分别表示树的结点个数、询问的个数和树根结点的序号。接下来 −1 行每行包含两个正整数 ,表示 结点和 结点之间有一条直接连接的边数据保证可以构成树。接下来 行每行包含两个正整数 ,表示询问 结点和 结点的最近公共祖先。输出格式输出包含 行每行包含一个正整数依次为每一个询问的结果。输入输出样例 #1输入 #15 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5输出 #14 4 1 4 4说明/提示对于 30% 的数据≤10≤10。对于 70% 的数据≤10000≤10000。对于 100% 的数据1≤,≤5×1051≤,,,≤不保证≠。样例说明该树结构如下第一次询问2,4 的最近公共祖先故为 4。第二次询问3,2 的最近公共祖先故为 4。第三次询问3,5 的最近公共祖先故为 1。第四次询问1,2 的最近公共祖先故为 4。第五次询问4,5 的最近公共祖先故为 4。故输出依次为 4,4,1,4,4。2021/10/4 数据更新 fstqwq应要求加了两组数据卡掉了暴力跳。这题是最近公共祖先(LCA)的标准模板题我们可以预处理出两点上跳的行为定义dp[i][j]:从节点i出发走2^j步能到达的节点那么类似于ST表{lastposdp[i][j-1]dp[i][j]dp[lastpos][j-1]}就是先走2^(j-1)步走到lastpos再从lastpos走2^(j-1)步到达节点dp[lastpos][j-1]总步数2(j-1)2(j-1)2^j起点i终点dp[lastpos][j-1]dp[i][j]所以递推式就是dp[i][j]dp[dp[i][j-1][j-1]还有一点就是我们用dp[i][0]记录i的父亲节点这些都可以用dfs来解决void dfs(int pos,int fa){ deep[pos]deep[fa]1; dp[pos][0]fa; for(auto v:g[pos]){ if(vfa) continue; dfs(v,pos); } } -----再者就是LCA函数先传入两个节点xy确保deepxdeep[y]那么显然的要求y节点先跳上与x节点等高的位置int ddeep[y]-deep[x]; for(int k0;k20;k){ if(dk1) ydp[y][k]; }如果xy说明两者的LCA就是xif(xy) return x;如果x!y:那就一起往上跳注意要从最大的步数开始跳因为从最小步数开始跳的话一旦答案再很高的位置就会浪费很多时间复杂度for(int k20;k0;k--){ if(dp[x][k]!dp[y][k]) //如果发现跳了这么多步还没有公共的节点 xdp[x][k],ydp[y][k]; //直接跳就不用再中间的节点了省时省力 }跳到最后xy都离最近公共祖先差一个位置直接c return dp[x][0](或者c return dp[y][0]一样的)ACcode:#includebits/stdc.h using namespace std; const int N5e55; int n,m,s; int dp[N][25],deep[N]; //fatherdp[i][0]; vectorint g[N]; /* dp[i][j]:从节点i往上跳2^j步达到的节点编号 lastposdp[i][j-1] 先从i跳2^(j-1)步 dp[i][j]dp[lastpos][j-1] 再从lastpos跳2^(j-1)步 所以dp[i][j]dp[dp[i][j-1]][j-1]; */ void dfs(int pos,int fa){ deep[pos]deep[fa]1; dp[pos][0]fa; for(auto v:g[pos]){ if(vfa) continue; dfs(v,pos); } } int LCA(int x,int y){ if(deep[x]deep[y]) swap(x,y); int ddeep[y]-deep[x]; for(int k0;k20;k) if(dk1) ydp[y][k]; if(xy) return x; //倒序先大步跳 for(int k20;k0;k--) if(dp[x][k]!dp[y][k]) xdp[x][k],ydp[y][k]; return dp[x][0]; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cinnms; for(int i1;in-1;i){ int x,y; cinxy; g[x].push_back(y); g[y].push_back(x); } dfs(s,s); for(int j1;j20;j) for(int i1;in;i) dp[i][j]dp[dp[i][j-1]][j-1]; while(m--){ int x,y; cinxy; coutLCA(x,y)endl; } return 0;