2 条题解

  • 0
    @ 2025-10-8 17:04:53
    #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
      @ 2025-10-8 17:04:37
      #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

      *【LCA最近公共祖先】[AHOI2008] 紧急集合 / 聚会

      信息

      ID
      3497
      时间
      1000ms
      内存
      256MiB
      难度
      10
      标签
      递交数
      8
      已通过
      4
      上传者