首页 > 其他分享 >AcWing1172. 祖孙询问

AcWing1172. 祖孙询问

时间:2023-01-02 17:56:48浏览次数:35  
标签:输出 AcWing1172 idx int 询问 depth 祖孙 root

题目描述

给定一棵包含 \(n\) 个节点的有根无向树,节点编号互不相同,但不一定是 \(1 \sim n\)。

有 \(m\) 个询问,每个询问给出了一对节点的编号 \(x\) 和 \(y\),询问 \(x\) 与 \(y\) 的祖孙关系。

对于每一个询问,若\(x\) 是 \(y\)的祖先则输出 \(1\),若 \(y\) 是 \(x\) 的祖先则输出 \(2\),否则输出 \(0\)。

解题思路

\(\qquad\)显然这题可以转化为:(记\(p\) 为\(x\) 和 \(y\)的最近公共祖先),如果\(x=p\)输出\(1\),如果\(y=p\)输出\(2\),否则输出\(0\),然后就可以用倍增求\(LCA\)了

代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int depth[N], f[N][20], n, m, root;

void add(int a, int b) 
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void prework(int root) 
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    queue<int> q; q.push(root);
    
    while (q.size()) 
    {
        auto t = q.front(); q.pop();
        
        for (int i = h[t]; ~i; i = ne[i]) 
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1) 
            {
                depth[j] = depth[t] + 1;
                f[j][0] = t, q.push(j);
                for (int k = 1; k <= 15; k ++ ) 
                    f[j][k] = f[f[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int x, int y) 
{
    if (depth[x] < depth[y]) swap(x, y);
    for (int i = 15; ~i; i -- ) 
    {
        int tmp = f[x][i];
        if (depth[tmp] >= depth[y]) x = tmp;
    }
    
    if (x == y) return x;
    
    for (int i = 15; ~i; i -- ) 
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    
    return f[x][0];
}

int main() 
{
    scanf("%d", &n);
    
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) 
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (b == -1) root = a;
        add(a, b), add(b, a);
    }
    
    prework(root);
    
    scanf("%d", &m);
    while (m -- ) 
    {
        int x, y;
        scanf("%d%d", &x, &y);
        int p = lca(x, y);
        if (x == p) puts("1");
        else if (y == p) puts("2");
        else puts("0");
    }
    
    return 0;
}

标签:输出,AcWing1172,idx,int,询问,depth,祖孙,root
From: https://www.cnblogs.com/StkOvflow/p/17020275.html

相关文章

  • 记录一次线上慢sql查询问题
        昨天晚上上线后,发现在app查询功能时候,整个系统直接爆出大量的慢sql报警。紧急回滚后查找问题,然后执行sql的执行计划:      发现有一个全表扫描的问......
  • [Algorithm] 双关键字查询问题
    问题现在米尔科村的考试时间。每个人都想尽可能不费吹灰之力地通过考试,这并不容易。米尔科意识到,对他来说,最好是找到比他了解更多的人,并向他们学习。每个人都跟着,现在每个......
  • C++ 类的项目练习 定义一个类,来表示某模拟养成游戏中人物: 每个人物, 有昵称,年龄,性别,
    Hero.h:#pragmaonce#include<iostream>#include<string>#include<vector>#include<sstream>usingnamespacestd;typedefenumgender{Man,//男W......
  • MySQL连接分页查询问题
    问题两表连接查询分页,如果不进行排序,则分页不准确,这将导致第一页出现的数据会在后几页再次出现,而且每次查询第一页结果都不一致解决连接查询分页必须按主键分页才能保证......
  • 【学习笔记】《范围修改查询问题》
    参考自APIO2022清华大学李欣隆的课件《范围修改查询问题》。其实感觉目前实用性不强(问题描述给定集合\(I\),令\(n=|I|\)。给定交换半群\((D,+)\),半群\((M,*)\)。......
  • 11.CF522D Closest Equals 线段树+离线询问
    11.CF522DClosestEquals线段树+离线询问给定序列,查询区间内距离最近的两个相等元素。离线查询,按右端点加入贡献计算答案即可洛谷传送门:​​CF522DClosestEquals-洛谷......
  • 金蝶ERP物料代码模糊查询问题
     最近遇到一个问题,公司帐套中在使用物料代码提取对应物料明细时,单据页不显示结果,只以最左侧代码查找,此时自定义物料代码是没有起作用的。后来网上搜索一遍没有结果,最后用......
  • loj10135.「一本通 4.4 练习 2」祖孙询问
    SLOJP10135.「一本通4.4练习2」祖孙询问题目描述已知一棵n个节点的有根树。有m个询问,每个询问给出了一对节点的编号x和y,询问x与y的祖孙关系。输入格式输入第一行......
  • LOJ #6208. 树上询问
    题目链接:​​传送门​​线段树维护每个点的k,t,d当做懒标记来维护这就需要对懒标记的理解了#include<bits/stdc++.h>#defineusingnamespacestd;typedeflonglongll;......
  • BZOJ 4320(ShangHai2006 Homework-询问分段+并查集)
    Description1:在人物集合S中加入一个新的程序员,其代号为X,保证X在当前集合中不存在。2:在当前的人物集合中询问程序员的modY最小的值。(为什么统计这个?因为拯救过......