E.1-Trees and Queries 最近公共祖先LCA

比眉伴天荒 2023-05-28 14:14 2阅读 0赞

早就知道这个算法了，但是懒得一直没有去学他，现在发现其实挺简单的算法——LCA（记录深度+倍增法求最近公共祖先）

任意两点距离=dep\[x\]+dep\[y\]-2\*dep\[lca(x,y)\];

E题 就是个裸的求LCA的题

给你一棵树，多次询问如果在x,y两个节点加上一边后，a到b的路径是否可以有k条边（可以重复走边）

可以重复走边那就看奇偶性，直接走（不用新连的边） 或者一个走到x，一个走到y后+1后看是否小于k且奇偶性与k相同（用上新连的边）

参考博客：[https://blog.csdn.net/chenyume/article/details/104340928][https_blog.csdn.net_chenyume_article_details_104340928]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll N=1e5+7;
    vector<int>son[N];
    int dep[N];///记录深度
    int fa[N][19];///倍增法找最近公共祖先
    void dfs(int x,int last)
    {
        fa[x][0]=last;
        dep[x]=dep[last]+1;
        for(int i=1;i<=18;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
        for(int i=0;i<son[x].size();i++)
        {
            if(son[x][i]==last)continue;
            dfs(son[x][i],x);
        }
    }
    int LCA(int x,int y)
    {
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=18;i>=0;i--)
            if(dep[fa[x][i]]>=dep[y])
                x=fa[x][i];
        if(x==y) return x;
        for(int i=18;i>=0;i--)
            if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
    int getlen(int x,int y)
    {
        int lca=LCA(x,y);
        return dep[x]+dep[y]-2*dep[lca];
    }
    bool check(int len,int k)
    {
        return len<=k&&(((len%2)^(k%2))==0);
    }
    int main()
    {
       int n;
       cin>>n;
       for(int i=1;i<n;i++)
       {
           int a1,a2;
           cin>>a1>>a2;
           son[a1].push_back(a2);
           son[a2].push_back(a1);
       }
       dfs(1,0);
       int m;
       cin>>m;
       while(m--)
       {
           int x,y,a,b,k;
           cin>>x>>y>>a>>b>>k;
           int len=getlen(a,b);
           bool f=0;
           if(check(len,k)){cout<<"YES"<<endl; continue;}
           len=getlen(x,a)+getlen(y,b)+1;
           if(check(len,k)){cout<<"YES"<<endl; continue;}
           len=getlen(x,b)+getlen(y,a)+1;
           if(check(len,k)){cout<<"YES"<<endl; continue;}
           cout<<"NO"<<endl;
       }
    }

[https_blog.csdn.net_chenyume_article_details_104340928]: https://blog.csdn.net/chenyume/article/details/104340928