Timus 1329. Galactic History。LCA最近公共祖先或dfs递归离线处理！

1329. Galactic History

比赛的时候看到学弟A了这题然后跟榜做，结果在LCA的道路上一去不复返，这个题是很像LCA求最近公共祖先的，不过三个人都没学过LCA，只能拿着资料看着像然后就打上去，结果debug半天，真是吃鸡，边学边做。

题意：n个点，接下来n行每行每个u,v,表示v是u的父节点。v=-1表示u是祖先节点。然后q次查询，每次一个u，v。如果u是v所在的子树的根，输出1，如果v是u所在的子树的根，输出-2，否则输出0。

思路：我们可以先dfs或bfs将这颗树分层，最朴素的思路肯定是从下层往上层查找，基于这个我们想到了LCA的复杂度，如果一层一层找肯定时TLE，亲测有TLE。但我们就想用二分法确定公共祖先，但模板是两个节点同时往上走到同一节点，这题我们需要判断两个节点是否在同一条链中。比赛时间不多，赛后才知道我们dfs递归的时候可以用时间戳来标记节点，如果两个点在同一条链中其时间戳是否一定的关系的，每个点用两个时间戳表示进和出的时间，这样就很好判断了。

int ru[N],chu[N],dep;

vector<int>g[N];

void init()

{

    memset(ru,0,sizeof(ru));

    memset(chu,0,sizeof(chu));

    for(int i=1;i<N;i++) g[i].clear();

}

void dfs(int v,int u)

{

    ru[v]=dep++;

    for(int i=0;i<g[v].size();i++)

        if(g[v][i]!=u) dfs(g[v][i],v);

    chu[v]=dep-1;

}

int main()

{

    int n,m;

    while(~scanf("%d",&n))

    {

        int root=0,u,v;

        init();

        for(int i=1;i<=n;i++)

        {

            scanf("%d%d",&u,&v);

            if(v!=-1) g[v].push_back(u);

            if(v==-1) root=u;

        }

        dep=0;

        dfs(root,-1);

        scanf("%d",&m);

        while(m--)

        {

            scanf("%d%d",&u,&v);

            if(ru[u]<=ru[v]&&chu[u]>=chu[v]) puts("1");

            else if(ru[u]>=ru[v]&&chu[u]<=chu[v]) puts("2");

            else puts("0");

        }

    }

    return 0;

}

思路二：不甘于昨天那种LCA的写法，今天又重新调出来debug了一下终于还是用LCA过了。

和上述说的差不多，LCA求最近公共祖先，从下层往上走，一直逼近，最后到同一层，这个题还没有LCA这么麻烦，我们只需判断从下层往上走到达同一层是否会重合，是的话说明这两个点在同一条链中。先dfs预处理深度和父节点，然后用倍增优化，p[k][v]表示v点往上走2^k层到达的点，预处理出来我们每次就可以在O（logn）内查找了。

vector<int>g[N];

int n,m,p[20][N],d[N],node[N];

void init1()

{

    memset(p,0,sizeof(p));

    memset(d,0,sizeof(d));

    for(int i=0; i<N; i++)  g[i].clear();

}

void dfs(int v,int u,int dep)

{

    p[0][v]=u;

    d[v]=dep;

    int len=g[v].size();

    for(int j=0; j<len; j++)

        if(g[v][j]!=u)

            dfs(g[v][j],v,dep+1);

}

void init()

{

    for(int k=0; k<17; k++)

        for(int i=1; i<=n; i++)

            if(p[k][node[i]]<0) p[k+1][node[i]]=-1;

            else p[k+1][node[i]]=p[k][p[k][node[i]]];

}

bool lca(int u,int v)

{

        for(int k=0; k<17&&d[u]>d[v]&&u!=-1; k++)//倒着来也行，从17到0

        {

            if((d[u]-d[v])>>k&1)

                u=p[k][u];

//            else break;

//        printf("%d %d %d\n",k,u,p[k][u]);

        }

    return u==v;

}

int main()

{

    while(~scanf("%d",&n))

    {

        init1();

        int u,v,root=0;

        for(int i=1; i<=n; i++)

        {

            scanf("%d%d",&node[i],&v);

            if(v!=-1) g[v].push_back(node[i]);

            else root=node[i];

        }

        dfs(root,-1,0);

        init();

        scanf("%d",&m);

        while(m--)

        {

            scanf("%d%d",&u,&v);

            if(d[v]>d[u])

            {

                if(lca(v,u)) puts("1");

                else puts("0");

            }

            else if(d[u]>d[v])

            {

                if(lca(u,v)) puts("2");

                else puts("0");

            }

            else puts("0");

        }

    }

    return 0;

}

巴特西

Timus 1329. Galactic History。LCA最近公共祖先或dfs递归离线处理！

1329. Galactic History

最新文章

热门文章