首页 > 其他 > 详细

P3379 【模板】最近公共祖先(LCA)(LCT)

时间:2019-01-12 10:21:32      阅读:28      评论:0      收藏:0      [点我收藏+]

标签:inline   link   多叉树   下一个   表示   int   cte   提示   接下来   

\(\color{#0066ff}{ 题目描述 }\)

如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。

\(\color{#0066ff}{输入格式}\)

第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。

接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。

\(\color{#0066ff}{输出格式}\)

输出包含M行,每行包含一个正整数,依次为每一个询问的结果。

\(\color{#0066ff}{输入样例}\)

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

\(\color{#0066ff}{输出样例}\)

4
4
1
4
4

\(\color{#0066ff}{数据范围与提示}\)

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=10

对于70%的数据:N<=10000,M<=10000

对于100%的数据:N<=500000,M<=500000

\(\color{#0066ff}{ 题解 }\)

拿LCT只为了求个LCA

有毒啊

access的时候记录一下上一个点(下一个链尾)

access第二个点的时候,最后一次的那个链的接触点就是LCA

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL in() {
    char ch; int x = 0, f = 1;
    while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
    for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
    return x * f;
}
const int maxn = 5e5 + 5;
struct LCT {
protected:
    struct node {
        node *ch[2], *fa;
        int rev;
        node(int rev = 0): rev(rev) { ch[0] = ch[1] = fa = NULL; }
        bool ntr() { return fa && (fa->ch[1] == this || fa->ch[0] == this); }
        bool isr() { return fa->ch[1] == this; }
        void trn() { std::swap(ch[0], ch[1]); rev ^= 1; }
        void dwn() { if(rev) { if(ch[0]) ch[0]->trn(); if(ch[1]) ch[1]->trn(); rev = 0; } }
    }s[maxn], *t[maxn], *lst;
    int top;
    void rot(node *x) {
        node *y = x->fa, *z = y->fa; int k = x->isr(); node *w = x->ch[!k];
        if(y->ntr()) z->ch[y->isr()] = x;
        x->ch[!k] = y, y->ch[k] = w;
        y->fa = x, x->fa = z;
        if(w) w->fa = y;
    }
    void splay(node *o) {
        t[top = 1] = o;
        while(t[top]->ntr()) t[top + 1] = t[top]->fa, top++;
        while(top) t[top--]->dwn();
        while(o->ntr()) { if(o->fa->ntr()) rot(o->isr() ^ o->fa->isr()? o : o->fa); rot(o); }
    }
    void access(node *x) { for(node *y = NULL; x; x = (y = x)->fa) splay(x), x->ch[1] = y, lst = x; }
    void makeroot(node *x) { access(x), splay(x), x->trn(); }
    node *findroot(node *x) { access(x), splay(x); while(x->dwn(), x->ch[0]) x = x->ch[0]; return splay(x), x; }
    node *getLCA(node *x, node *y) { return access(x), access(y), lst; }
    void link(node *x, node *y) { makeroot(x), x->fa = y; }
public:
    void link(int x, int y) { link(s + x, s + y); }
    int LCA(int x, int y) { return getLCA(s + x, s + y) - s; }
    void makeroot(int x) { makeroot(s + x); }
}v;
int main() {
    int n = in(), m = in(), s = in();
    for(int i = 1; i < n; i++) v.link(in(), in());
    v.makeroot(s);
    while(m --> 0) printf("%d\n", v.LCA(in(), in()));
    return 0;
}

P3379 【模板】最近公共祖先(LCA)(LCT)

标签:inline   link   多叉树   下一个   表示   int   cte   提示   接下来   

原文:https://www.cnblogs.com/olinr/p/10258553.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号