首页 > 其他分享 >CF519E A and B and Lecture Rooms

CF519E A and B and Lecture Rooms

时间:2023-06-23 14:13:26浏览次数:120  
标签:sz return idx int -- dep CF519E Lecture Rooms

题目链接

题目

见链接。

题解

知识点:倍增,LCA,树型dp。

要找到距离两点 \(u,v\) 相同的点个数,我可以分类讨论:

  1. \(u,v\) 是同一个点,那么全部点都可以。
  2. \(u,v\) 处于相同深度,那么就是全部点减去 \(LCA(u,v)\) 的 \(u,v\) 两点所在子树的全部点。
  3. \(u,v\) 不在相同深度,当 \(u,v\) 距离为奇数时无解,否则解为 \(u,v\) 路径中点为根的子树全部点减去中点的 \(u,v\) 中是中点子孙的点所在子树的全部点。

其中,查询过程用倍增很容易实现,子树大小用树型dp即可。

时间复杂度 \(O((n+m) \log n)\)

空间复杂度 \(O(n \log n)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Graph {
    struct edge {
        int v, nxt;
    };
    int idx;
    vector<int> h;
    vector<edge> e;

    Graph(int n = 0, int m = 0) { init(n, m); }

    void init(int n, int m) {
        idx = 0;
        h.assign(n + 1, 0);
        e.assign(m + 1, {});
    }

    void add(int u, int v) {
        e[++idx] = { v,h[u] };
        h[u] = idx;
    }
};

const int N = 100007;
Graph g;

int dep[N], f[27][N], sz[N];
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    f[0][u] = fa;
    sz[u] = 1;
    for (int i = 1;i <= 18;i++)
        f[i][u] = f[i - 1][f[i - 1][u]];
    for (int i = g.h[u];i;i = g.e[i].nxt) {
        int v = g.e[i].v;
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20;i >= 0;i--) {
        if (dep[f[i][u]] >= dep[v])u = f[i][u];
        if (u == v) return u;
    }
    for (int i = 20;i >= 0;i--) {
        if (f[i][u] != f[i][v]) {
            u = f[i][u];
            v = f[i][v];
        }
    }
    return f[0][u];
}

int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; }

int get_ans(int u, int v) {
    if (u == v) return sz[1];
    if (dep[u] == dep[v]) {
        for (int i = 20;i >= 0;i--) {
            if (f[i][u] != f[i][v]) {
                u = f[i][u];
                v = f[i][v];
            }
        }
        return sz[1] - sz[u] - sz[v];
    }
    int dis = dist(u, v);
    if (dis & 1) return 0;
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dis / 2;
    for (int i = 20;i >= 0;i--)
        if (dep[f[i][u]] > d) u = f[i][u];
    return sz[f[0][u]] - sz[u];
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    g.init(n, n << 1);
    for (int i = 1;i <= n - 1;i++) {
        int u, v;
        cin >> u >> v;
        g.add(u, v);
        g.add(v, u);
    }

    dfs(1, 0);

    int m;
    cin >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << get_ans(u, v) << '\n';
    }
    return 0;
}

标签:sz,return,idx,int,--,dep,CF519E,Lecture,Rooms
From: https://www.cnblogs.com/BlankYang/p/17499084.html

相关文章

  • Codeforces Round #287 (Div. 2)-D. The Maths Lecture(数位dp)
    原题链接D.TheMathsLecturetimelimitpertestmemorylimitpertestinputoutputAmrdoesn'tlikeMathsashefindsitreallyboring,soheusuallysleepsinMathsl......
  • 23-05-20 总结 Meeting rooms 系列3个题目
    题目列表:P1.【easy,会员】MeetingRooms-LeetCodeP2.【Mid,会员】MeetingRoomsII-LeetCodeP3.MeetingRoomsIII-LeetCodeP1.会员题,检测会议是否安排得开思路:非常简单,直接按starttime进行排序,然后检测是否有overlap即可时间:O(nlogn),空间:O(1)classSolut......
  • 【Introductory Biology】Lecture 7 - Replication 复制
    文章目录SlidesRefDNA复制是指DNA双链在细胞分裂间期阶段进行以一个亲代DNA分子为模板合成子代DNA链的过程。复制的结果是一条双链变成两条一样的双链(如果复制过程正常的话),每条双链都与原来的双链一样(排除突变等不定因素)。参与DNA复制叉工作的许多酶。SlidesRef【麻省理工公开课】......
  • 【Introductory Biology】Lecture 12 - Chemical Genetics 1 - Cell Division & Segre
    文章目录SlidesRefSlidescentraldogma中心法则…Andwe’regoingtostarttalkingabouthowinformationflowsbetweencells,sofromaparentcelltoitsdaughtercells.Andwe’realsogonnatalkabouthowinformationflowsfromgenerationtothenext.Andth......
  • [CMU 15-418] (Lecture4) Parallel Programming Basics
    本系列文章为CMU15-418/15-618:ParallelComputerArchitectureandProgramming,Fall2018课程学习笔记课程官网:CMU15-418/15-618:ParallelComputerArchitectureandProgramming参考文章:CMU15-418notes相关资源与介绍:CMU15-418/StanfordCS149:ParallelComput......
  • [CMU 15-418] Lecture2 A Modern Multi-Core Processor
    本系列文章为CMU15-418/15-618:ParallelComputerArchitectureandProgramming,Fall2018课程学习笔记课程官网:CMU15-418/15-618:ParallelComputerArchitectureandProgramming参考文章:CMU15-418notes相关资源与介绍:CMU15-418/StanfordCS149:ParallelComput......
  • [CMU15-418] Lecture1 Why Parallelism
    本系列文章为15-418/15-618:ParallelComputerArchitectureandProgramming,Fall2018课程学习笔记课程官网:参考文章:相关资源与介绍:Theme1Theme2Theme3SummaryILP(instructionlevelparallelism)指令级并行不能一直增长,因为一个程序中出现若干不相关指令......
  • Lecture#20 Database Crash Recovery
    上节课介绍到,故障恢复算法由两个部分构成:在事务执行过程中采取的行动来确保出现故障时能够恢复(上节课)在故障发生后的恢复机制,确保原子性、一致性和持久性(本节课)1ARIES本节课介绍的是AlgorithmsforRecoveryandIsolationExploitingSemantics(ARIES),由IBMRese......
  • Lecture#13 Query Processing2
    我们在Lec12中已经讨论了怎么将operators组织为一个queryplan。当时我们是假设query是由一个worker(是DBMS的组件,负责代表客户机执行任务并返回结果,可能是一个线程或进程)执行。然而在实践中,query往往是由多个workers并发执行。并发执行为DBMS提供了很多好处:r......
  • Lecture#12 Query Processing1
    1QueryPlan通常一个SQL语句会被组织成如图的树状查询计划,数据从叶节点流到根节点,查询结果在根节点中得出。通常,树上的操作符operators是二元的(1~2个子运算符)。而本节将讨论在这样一个计划中,如何为这个数据流动过程建模,大纲如下:ProcessingModelsAccessMethodsEx......