2 条题解
-
0
#include<bits/stdc++.h> #define eb emplace_back using namespace std; const int N=5e5+10; vector<int>G[N]; int f[N][21], D, dep[N]; void dfs(int x, int fa) { dep[x] = dep[fa] + 1; f[x][0] = fa; for(int i=1; i<=D; i++) f[x][i] = f[f[x][i-1]][i-1]; for(int y : G[x]) if(y != fa) dfs(y, x); } int lca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); for(int i=D; i>=0; i--) if(dep[f[x][i]] >= dep[y]) x = f[x][i]; if(x == y) return x; for(int i=D; i>=0; i--) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; } int dis(int x, int y){ return dep[x] + dep[y] - 2 * dep[lca(x, y)]; } int main() { int n, m; scanf("%d%d", &n, &m); for(int i=1, x, y; i < n; i++) scanf("%d%d", &x, &y), G[x].eb(y), G[y].eb(x); dep[0] = 0; D = log2(n); dfs(1, 0); for(int i=1, x, y, z; i <= m; i++) { scanf("%d%d%d", &x, &y, &z); int p1 = lca(x, y), d1 = dis(x, y) + dis(p1, z); int p2 = lca(x, z), d2 = dis(x, z) + dis(p2, y); int p3 = lca(y, z), d3 = dis(y, z) + dis(p3, x); if(d1 > d2) swap(p1, p2), swap(d1, d2); if(d1 > d3) swap(p1, p3), swap(d1, d3); printf("%d %d\n", p1, d1); } return 0; } -
0
#include<bits/stdc++.h> #define eb emplace_back using namespace std; const int N=5e5+10; vector<int>G[N]; int f[N][21],D,dep[N]; void dfs(int x,int fa) { dep[x]=dep[fa]+1; f[x][0]=fa;for(int i=1;i<=D;i++)f[x][i]=f[f[x][i-1]][i-1]; for(int y:G[x])if(y!=fa)dfs(y,x); } int lca(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=D;i>=0;i--) if(dep[f[x][i]]>=dep[y])x=f[x][i]; if(x==y) return x; for(int i=D;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } int dis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];} int main() { int n,m;scanf("%d%d",&n,&m); for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].eb(y),G[y].eb(x); dep[0]=0;D=log2(n);dfs(1,0); for(int i=1,x,y,z;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); int p1=lca(x,y),d1=dis(x,y)+ dis(p1,z); int p2=lca(x,z),d2=dis(x,z)+ dis(p2,y); int p3=lca(y,z),d3=dis(y,z)+ dis(p3,x); if(d1>d2) swap(p1,p2),swap(d1,d2); if(d1>d3) swap(p1,p3),swap(d1,d3); printf("%d %d\n",p1,d1); } return 0; }
- 1
信息
- ID
- 3497
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 8
- 已通过
- 4
- 上传者