Menu
Article ACM

LCA专题

NodeKey

NodeKey

• 12 min read

本文起始请听我先说一句

***的HDU4429!!!!!!!!!

这道题是我想自己写个LCA专题的起因。你要是去google题解的话全是用暴力求得。不知道为什么，你写题写到后面你会发现题解的代码全特么一个样子。说明他们很可能是不太懂，然后从某一个博客中看了代码，照样子写了，然后A了就得过且过的样子。当然我是不喜欢这样的。然后我就想用下tarjan求LCA，顺便复习一下算法。

结果！！！！

WA了两天！！！！

忍无可忍交了一发暴力，60ms 秒过！！！！！玛德，这题绝对有问题！！！！我现在就要开个专题先验证一下我自己的算法。

先是放一下我对这题的题解

HDU 4429 Split the Rectangle

附带本人评价：狗屎 好题

题意：
给你一个矩形，再给你一些边，这些边用来分割矩形。
再是几次询问，每次询问给你两个点，要求你每次删去几条边，使得这两个点在同一个矩形中，问此时剩下的矩形数最多还有多少。

思路：
每次分割矩形后，使所形成的两个小矩形成文被分割矩形的两个孩子。如此这般就会形成一棵二叉树。
每次查询求出两个点所在的叶子节点，再求出这两个节点的LCA就是他们最优的矩形解。得到 ans = 总矩形数目
-LCA为根节点的子树中的矩形数目（就是叶子节点数目）。

暴力求解Code
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2010;
int idx, n;
int num[maxn];

struct rectangle {
    int x1, x2, y1, y2;
    void setPoint(int a, int b, int c, int d)
    {
        x1 = a;
        y1 = b;
        x2 = c;
        y2 = d;
    }
};

struct node {
    rectangle rec;
    int dep, father;
    int left, right;
} tree[maxn << 1];

inline bool judgeIn(rectangle& rec, int& x, int& y)
{
    return x >= rec.x1 && x <= rec.x2 && y >= rec.y1 && y <= rec.y2;
}

inline int getIdx(int x, int y)
{
    int r = 0, t;
    while (true) {
        t = tree[r].left;
        if (t == -1)
            return r;
        if (judgeIn(tree[t].rec, x, y))
            r = t;
        else
            r = tree[r].right;
    }
}

void addEdge(int cur, rectangle& a)
{
    rectangle& father_rec = tree[cur].rec;
    if (a.x1 == a.x2) {
        tree[idx].rec.setPoint(father_rec.x1, father_rec.y1, a.x2, a.y2);
        tree[idx].father = cur;
        tree[cur].left = idx++;

        tree[idx].rec.setPoint(a.x1, a.y1, father_rec.x2, father_rec.y2);
        tree[idx].father = cur;
        tree[cur].right = idx++;
    } else if (a.y1 == a.y2) {
        tree[idx].rec.setPoint(a.x1, a.y1, father_rec.x2, father_rec.y2);
        tree[idx].father = cur;
        tree[cur].left = idx++;

        tree[idx].rec.setPoint(father_rec.x1, father_rec.y1, a.x2, a.y2);
        tree[idx].father = cur;
        tree[cur].right = idx++;
    }
}

int getTreeNumber(int cur, int dep)
{
    num[cur] = 0;
    tree[cur].dep = dep;
    int left = tree[cur].left, right = tree[cur].right;
    if (~left && num[left] == -1)
        num[cur] += getTreeNumber(left, dep + 1);
    if (~right && num[right] == -1)
        num[cur] += getTreeNumber(right, dep + 1);
    return (left == -1 && right == -1) ? 1 : num[cur];
}

void init()
{
    idx = 1;
    for (int i = 0; i <= 2 * n + 10; i++) {
        tree[i].left = tree[i].right = -1;
        num[i] = head[i] = -1;
    }
}

int main()
{
    int q, u, v;
    rectangle tmp;
    while (scanf("%d %d %d %d", &tmp.x1, &tmp.y1, &tmp.x2, &tmp.y2) != EOF) {
        tree[0].rec = tmp;
        scanf("%d %d", &n, &q);
        init();
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d %d", &tmp.x1, &tmp.y1, &tmp.x2, &tmp.y2);
            if (tmp.x1 == tmp.x2 && tmp.y1 > tmp.y2)
                swap(tmp.y1, tmp.y2);
            else if (tmp.y1 == tmp.y2 && tmp.x1 > tmp.x2)
                swap(tmp.x1, tmp.x2);
            addEdge(getIdx((tmp.x1 + tmp.x2) >> 1, (tmp.y1 + tmp.y2) >> 1), tmp);
        }
        getTreeNumber(0, 0);
        while (q--) {
            scanf("%d %d %d %d", &tmp.x1, &tmp.y1, &tmp.x2, &tmp.y2);
            u = getIdx(tmp.x1, tmp.y1);
            v = getIdx(tmp.x2, tmp.y2);
            if (u == v) {
                printf("%d\n", n + 1);
                continue;
            }
            while (u != v) {
                if (tree[u].dep < tree[v].dep)
                    v = tree[v].father;
                else if (tree[u].dep > tree[v].dep)
                    u = tree[u].father;
                else {
                    u = tree[u].father;
                    v = tree[v].father;
                }
            }
            printf("%d\n", n + 1 - num[u] + 1);
        }
    }
    return 0;
}
Tarjan 求解 Code

//代码略长

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2010;
int idx, n, query_idx;
int head[maxn];
int root[maxn], ans[maxn], dis[maxn], num[maxn];
bool vis[maxn];

struct query_node {
    int to, idx;
    int nxt;
} edges[maxn << 1];

struct rectangle {
    int x1, x2, y1, y2;
    void setPoint(int a, int b, int c, int d)
    {
        x1 = a;
        y1 = b;
        x2 = c;
        y2 = d;
    }
};

struct node {
    rectangle rec;
    int left, right;
} tree[maxn << 1];

inline bool judgeIn(rectangle& rec, int& x, int& y)
{
    return x >= rec.x1 && x <= rec.x2 && y >= rec.y1 && y <= rec.y2;
}

inline int getIdx(int x, int y)
{
    int r = 0, t;
    while (true) {
        t = tree[r].left;
        if (t == -1)
            return r;
        if (judgeIn(tree[t].rec, x, y))
            r = t;
        else
            r = tree[r].right;
    }
}

void addEdge(int cur, rectangle& a)
{
    rectangle& father_rec = tree[cur].rec;
    if (a.x1 == a.x2) {
        tree[idx].rec.setPoint(father_rec.x1, father_rec.y1, a.x2, a.y2);
        tree[cur].left = idx++;

        tree[idx].rec.setPoint(a.x1, a.y1, father_rec.x2, father_rec.y2);
        tree[cur].right = idx++;
    } else if (a.y1 == a.y2) {
        tree[idx].rec.setPoint(a.x1, a.y1, father_rec.x2, father_rec.y2);
        tree[cur].left = idx++;

        tree[idx].rec.setPoint(father_rec.x1, father_rec.y1, a.x2, a.y2);
        tree[cur].right = idx++;
    }
}

void addEdge(int u, int v, int d)
{
    edges[query_idx].to = v;
    edges[query_idx].idx = d;
    edges[query_idx].nxt = head[u];
    head[u] = query_idx++;
}

int fin(int x)
{
    return root[x] == x ? x : root[x] = fin(root[x]);
}

int getTreeNumber(int cur)
{
    num[cur] = 0;
    int left = tree[cur].left, right = tree[cur].right;
    if (~left && num[left] == -1)
        num[cur] += getTreeNumber(left);
    if (~right && num[right] == -1)
        num[cur] += getTreeNumber(right);
    return (left == -1 && right == -1) ? 1 : num[cur];
}

void tarjan(int u)
{
    root[u] = u;
    int left = tree[u].left, right = tree[u].right;
    if (~left && !vis[left]) {
        tarjan(left);
        root[left] = u;
    }
    if (~right && !vis[right]) {
        tarjan(right);
        root[right] = u;
    }

    vis[u] = true;
    for (int it = head[u]; ~it; it = edges[it].nxt) {
        int v = edges[it].to;
        if (vis[v]) {
            ans[edges[it].idx] = n + 2 - num[fin(v)];
            //printf("u:%d v:%d       LCA:%d  num[u]:%d\n", u, v, fin(v), num[fin(v)]);
        }
    }
    //printf("cur:%d left:%d right:%d\n", u, left, right);
}

void init()
{
    idx = 1;
    query_idx = 0;
    for (int i = 0; i <= 2 * n + 10; i++) {
        tree[i].left = tree[i].right = -1;
        num[i] = head[i] = -1;
        vis[i] = false;
        root[i] = i;
    }
}

int main()
{
    int q, u, v;
    rectangle tmp;
    while (scanf("%d %d %d %d", &tmp.x1, &tmp.y1, &tmp.x2, &tmp.y2) != EOF) {
        tree[0].rec = tmp;
        scanf("%d %d", &n, &q);
        init();
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d %d", &tmp.x1, &tmp.y1, &tmp.x2, &tmp.y2);
            if (tmp.x1 == tmp.x2 && tmp.y1 > tmp.y2)
                swap(tmp.y1, tmp.y2);
            else if (tmp.y1 == tmp.y2 && tmp.x1 > tmp.x2)
                swap(tmp.x1, tmp.x2);
            addEdge(getIdx((tmp.x1 + tmp.x2) >> 1, (tmp.y1 + tmp.y2) >> 1), tmp);
        }
        for (int i = 0; i < q; i++) {
            scanf("%d %d %d %d", &tmp.x1, &tmp.y1, &tmp.x2, &tmp.y2);
            u = getIdx(tmp.x1, tmp.y1);
            v = getIdx(tmp.x2, tmp.y2);
            if (u == v)
                ans[i] = n + 1;
            else {
                addEdge(u, v, i);
                addEdge(v, u, i);
            }
        }
        getTreeNumber(0);
        tarjan(0);
        for (int i = 0; i < q; i++)
            printf("%d\n", ans[i]);
    }
    return 0;
}

POJ 1330 Nearest Common Ancestors

题意：
一个测试组数，n，n-1条边，一个询问

思路：
标准入门模板题

#include <cstdio>
#include <cstring>

using namespace std;
const int maxn = 10010;

int n, idx, st, en, ans;
int head[maxn], root[maxn], num[maxn];
bool vis[maxn];

struct node {
    int v, nxt;
} edges[maxn << 1];

void addEdge(int u, int v)
{
    edges[idx].v = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

int fin(int x)
{
    return root[x] == x ? root[x] : root[x] = fin(root[x]);
}

void tarjan(int cur)
{
    root[cur] = cur;
    vis[cur] = true;
    if (cur == st && vis[en]) {
        ans = fin(en);
        return;
    } else if (cur == en && vis[st]) {
        ans = fin(st);
        return;
    }
    for (int it = head[cur]; ~it; it = edges[it].nxt) {
        int v = edges[it].v;
        if (!vis[v]) {
            tarjan(v);
            root[v] = cur;
        }
    }
}

void init()
{
    idx = 0;
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        vis[i] = false;
        num[i] = 0;
    }
}

int main()
{
    int T, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        for (int i = 0; i < n - 1; i++) {
            scanf("%d %d", &u, &v);
            addEdge(u, v);
            num[v]++;
        }
        scanf("%d %d", &st, &en);
        for (int i = 1; i <= n; i++) {
            if (num[i] == 0) {
                tarjan(i);
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

HDU 2586 How far away ?

经典LCA，水数据

题意：
让你求在一棵树上任意两个点的距离。

思路：
经典模板题。听说数据十分水，有很多人A的代码自己都能发现很多bug，从而写了假模板……，但我还是WA了很多发……

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define EDGE true
#define QUERY false

using namespace std;
const int maxn = 40005;
int n, q, idx, query_idx;

int head[maxn], num[maxn], ans[maxn], root[maxn], dis[maxn], query_head[maxn], qu[1000], qv[1000];
bool vis[maxn];

struct node {
    int to, nxt;
    int key;
} edges[maxn<<1], query[1000];

void addEdge(int u, int v, int key, bool type)
{
    if (type == EDGE) {
        edges[idx].key = key;
        edges[idx].to = v;
        edges[idx].nxt = head[u];
        head[u] = idx++;
    } else {
        query[query_idx].key = key;
        query[query_idx].to = v;
        query[query_idx].nxt = query_head[u];
        query_head[u] = query_idx++;
    }
}

int findRoot(int x)
{
    return root[x] == x ? x : root[x] = findRoot(root[x]);
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    for (int it = query_head[u]; ~it; it = query[it].nxt) {
        int v = query[it].to;
        if (vis[v])
            ans[query[it].key] = findRoot(v);
    }
    for (int it = head[u]; ~it; it = edges[it].nxt) {
        int v = edges[it].to;
        if (!vis[v]) {
            dis[v] = dis[u] + edges[it].key;
            tarjan(v);
            root[v] = u;
        }
    }
}

void init()
{
    query_idx = idx = 0;
    for (int i = 0; i <= n; i++) {
        query_head[i] = head[i] = -1;
        num[i] = 0;
        vis[i] = false;
    }
}

int main()
{
    int T, u, v, w;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &q);
        init();
        for (int i = 1; i < n; i++) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w, EDGE);
            addEdge(v, u, w, EDGE);
        }
        for (int i = 0; i < q; i++) {
            scanf("%d %d", qu + i, qv + i);
            addEdge(qu[i], qv[i], i, QUERY);
            addEdge(qv[i], qu[i], i, QUERY);
        }
        dis[1] = 0;
        tarjan(1);
        for (int i = 0; i < q; i++)
            printf("%d\n", dis[qu[i]] + dis[qv[i]] - 2 * dis[ans[i]]);
    }
    return 0;
}

HDU 4547 CD操作

LCA模板题

题意：
命令行中的 cd 操作，允许这两种操作

  • 从一个目录进入任意子孙目录
  • 返回上级目录

多次询问，从 u 到 v 至少进行几次 cd 操作。

思路：
很简单的模板题，一遍tanjan求出没对 u , v 的 lca，再是 dis[u] – dis[lca] + (v!=lca) 即为答案
应该是很好理解的，dis[x]表示 根节点到 x 节点的最短距离
dis[u]-dis[lca]表示 2 操作的次数，如果 目标节点就是lca，就不需要 1 操作，否则 +1 。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 5;

int n, q, tot, idx, q_idx;
int head[maxn], q_head[maxn];
int root[maxn], ans[maxn], dis[maxn], indegree[maxn];
bool vis[maxn];
int qu[maxn], qv[maxn];

map<string, int> key;

struct node {
    int to;
    int nxt;
} edges[maxn << 1];

struct q_node {
    int to;
    int nxt;
    int idx;
} q_edges[maxn << 1];

void addEdge(node* E, int u, int v)
{
    E[idx].to = v;
    E[idx].nxt = head[u];
    head[u] = idx++;
}

void addEdge(q_node* E, int u, int v, int idx)
{
    E[q_idx].idx = idx;
    E[q_idx].to = v;
    E[q_idx].nxt = q_head[u];
    q_head[u] = q_idx++;
}

void init()
{
    tot = 0;
    idx = 0;
    q_idx = 0;
    key.clear();
    memset(head, -1, sizeof head);
    memset(q_head, -1, sizeof q_head);
    memset(vis, false, sizeof vis);
    memset(indegree, 0, sizeof indegree);
}

int findRoot(int x)
{
    return root[x] == x ? x : root[x] = findRoot(root[x]);
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    for (int it = q_head[u]; ~it; it = q_edges[it].nxt) {
        int v = q_edges[it].to;
        if (vis[v])
            ans[q_edges[it].idx] = findRoot(v);
    }
    for (int it = head[u]; ~it; it = edges[it].nxt) {
        int v = edges[it].to;
        if (!vis[v]) {
            dis[v] = dis[u] + 1;
            tarjan(v);
            root[v] = u;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string us, vs;
    int T, u, v;
    cin >> T;
    while (T--) {
        cin >> n >> q;
        init();
        for (int i = 1; i < n; i++) {
            cin >> us >> vs;
            if (key.find(us) == key.end()) {
                u = tot;
                key[us] = tot++;
            } else
                u = key[us];
            if (key.find(vs) == key.end()) {
                v = tot;
                key[vs] = tot++;
            } else
                v = key[vs];
            addEdge(edges, v, u);
            indegree[u]++;
        }
        for (int i = 0; i < q; i++) {
            cin >> us >> vs;
            qu[i] = key[us];
            qv[i] = key[vs];
            addEdge(q_edges, qu[i], qv[i], i);
            addEdge(q_edges, qv[i], qu[i], i);
        }
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0) {
                dis[i] = 0;
                tarjan(i);
                break;
            }
        for (int i = 0; i < q; i++) {
            printf("%d\n", dis[qu[i]] - dis[ans[i]] + (ans[i] != qv[i]));
        }
    }
    return 0;
}

个人模板

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 5;

int n, q, idx, q_idx;
int head[maxn], q_head[maxn];
int root[maxn], lca[maxn], dis[maxn], indegree[maxn];
bool vis[maxn];
int qu[maxn], qv[maxn];

struct node {
    int to;
    int len;
    int nxt;
} edges[maxn << 1];

struct q_node {
    int to;
    int nxt;
    int idx;
} q_edges[maxn << 1];

void addEdge(node* E, int u, int v, int w)
{
    E[idx].to = v;
    E[idx].len = w;
    E[idx].nxt = head[u];
    head[u] = idx++;
}

void addEdge(q_node* E, int u, int v, int idx)
{
    E[q_idx].idx = idx;
    E[q_idx].to = v;
    E[q_idx].nxt = q_head[u];
    q_head[u] = q_idx++;
}

void init()
{
    idx = 0;
    q_idx = 0;
    memset(head, -1, sizeof head);
    memset(q_head, -1, sizeof q_head);
    memset(vis, false, sizeof vis);
    memset(indegree, 0, sizeof indegree);
}

int findRoot(int x)
{
    return root[x] == x ? x : root[x] = findRoot(root[x]);
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    for (int it = q_head[u]; ~it; it = q_edges[it].nxt) {
        int v = q_edges[it].to;
        if (vis[v])
            lca[q_edges[it].idx] = findRoot(v);
    }
    for (int it = head[u]; ~it; it = edges[it].nxt) {
        int v = edges[it].to;
        if (!vis[v]) {
            dis[v] = dis[u] + edges[it].len;
            tarjan(v);
            root[v] = u;
        }
    }
}

int main()
{
    int u, v, w;
    while (scanf("%d %d", &n, &q) != EOF) {
        init();
        for (int i = 1; i < n; i++) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(edges, u, v, w);
            indegree[v]++;
        }
        for (int i = 0; i < q; i++) {
            scanf("%d %d", qu + i, qv + i);
            addEdge(q_edges, qu[i], qv[i], i);
            addEdge(q_edges, qv[i], qu[i], i);
        }
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0) {
                dis[i] = 0;
                tarjan(i);
                break;
            }
        for (int i = 0; i < q; i++) {
            //根据题意输出
        }
    }
    return 0;
}

几个小结

  1. 树根到节点的距离求解 和 两点之间的距离求解必须分开。因为tarjan是由下往上的计算方法，而求距离则是由上往下求，所以不能同时求得。
  2. 很多人都喜欢使用在建图的时候直接建立无向边，然后再查询的时候直接 tarjan(1) ，这样写虽然很方便，而且也能节约 O(n) 的 时间和空间，但据我目前所知，只能单独对求两个点的距离没什么影响，如果略有变化。这样的写法就会出现错误 (比如第三道……) 所以我个人还是推荐使用建立有向边，再自行找出根节点的方法。
Share