LCA

POJ 3728 The merchant

Posted on

LCA 好题!

这道题我暂时只知道用Tarjan的解法。
Tarjan解法完美地运用了Tarjan的核心原理与性质:
深度优先搜索时的向下局部性。自己乱取得,蛤蛤蛤

题意:
给你一棵树,每个节点有一个权值。给你很多个询问,每个询问两个点。要你在给定点的树链上找到有序的最大差值。

思路:
首先考虑分治。设树链 u -> lca -> v
答案无非只有三种情况:

  1. u -> lca 的最大差值
  2. lca -> v 的最大差值
  3. lca -> v 的最大值 - u -> lca 的最小值

考虑dp维护这四个值。
因为运用Tarjan算法的时候,基于dfs,在你的眼里,当前节点就是向下整棵树的根节点,你完全不会去考虑往上的节点。
所以你现在使用的四个值,刚好是你当前节点的孩子节点的最优值。
基于这个事实,我们可以对其状态转移并维护。

AC Code

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int n;
int val[maxn], res[maxn];
int up[maxn], down[maxn], max_val[maxn], min_val[maxn];
int root[maxn];
bool vis[maxn];

vector<int> g[maxn];
vector<pii> q[maxn];
vector<pii> ans[maxn];

int findRoot(int x)
{
    if (root[x] == x)
        return x;
    int fa = root[x];
    root[x] = findRoot(root[x]);
    up[x] = max(up[x], max(up[fa], max_val[fa] - min_val[x]));
    down[x] = max(down[x], max(down[fa], max_val[x] - min_val[fa]));
    max_val[x] = max(max_val[x], max_val[fa]);
    min_val[x] = min(min_val[x], min_val[fa]);
    return root[x];
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    int sz = q[u].size();
    for (int i = 0; i < sz; i++) {
        int v = q[u][i].second;
        if (vis[v]) {
            int lca = findRoot(v);
            ans[lca].push_back(make_pair(u, i));
        }
    }
    sz = g[u].size();
    for (int i = 0; i < sz; i++) {
        int v = g[u][i];
        if (!vis[v]) {
            tarjan(v);
            root[v] = u;
        }
    }
    sz = ans[u].size();
    for (int i = 0; i < sz; i++) {
        int x = ans[u][i].first, y = q[x][ans[u][i].second].second;
        int id = q[x][ans[u][i].second].first;
        if (id < 0) {
            id = -id;
            swap(x, y);
        }
        findRoot(x), findRoot(y);
        res[id] = max(up[y], down[x]);
        res[id] = max(res[id], max_val[x] - min_val[y]);
    }
}

void init()
{
    for (int i = 0; i <= n; i++) {
        g[i].clear(), q[i].clear(), ans[i].clear();
        vis[i] = false;
        up[i] = down[i] = 0;
    }
}

int main()
{
    int u, v, qnum;
    while (scanf("%d", &n) != EOF) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", val + i);
            min_val[i] = max_val[i] = val[i];
        }
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        scanf("%d", &qnum);
        for (int i = 1; i <= qnum; i++) {
            scanf("%d %d", &u, &v);
            q[u].push_back(make_pair(-i, v));
            q[v].push_back(make_pair(i, u));
        }
        tarjan(1);
        for (int i = 1; i <= qnum; i++)
            printf("%d\n", res[i]);
    }
    return 0;
}
LCA

CodeForces 832D Misha, Grisha and Underground

Posted on

昨晚疯狂掉分的第四题,其实比第三题还简单……
搞不懂cf又不按套路出牌了……先是来一个巨简单的,让每个人都不得不去签到,随后是坑题,然后是压轴题,再然后才是普通题,难题……

题意:
给你一棵树,每次询问3个点,要你求出3个点两两构成的路径中选出两条,使得他们相交的长度最长。

思路:
这道题并不难,先求出LCA,再分类讨论一下即可,但是但是但是但是!!分类的情况会非常非常多,就图而言就有4种,还要考虑各自的位置。
必须得总结一下,不然跟着写会疯掉。
考虑让每个点为两条路径的相交点,分三种情况讨论。
而每种情况中,当两个路径各自的lca相同时,除了该点的所在的路径以外只要求出另外两个点的lca长度 - 三点lca 路径长度即可。
否则,就只剩下第三个点为另外两点的父亲这一情况,所以长度为 根节点到所讨论的结点距离 减去 非父亲结点的另外两个结点的 lca 的距离。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary));

const int maxn = 1e5 + 5;

int n, q, v, idx = 1, qidx = 1;
int head[maxn], qhead[maxn];
bool vis[maxn];
int root[maxn];
int lca[maxn * 3], dis[maxn];

struct node {
    int to, next;
    node() {}
    node(int _to, int _next) { to = _to, next = _next; }
} edges[maxn * 2];

struct qnode {
    int to, next, idx;
    qnode() {}
    qnode(int _to, int _next, int _idx) { to = _to, next = _next, idx = _idx; }
} qedges[maxn * 6];

int a[maxn], b[maxn], c[maxn];

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

void addQEdge(int u, int v, int id)
{
    qedges[qidx] = qnode(v, qhead[u], id);
    qhead[u] = qidx++;
    qedges[qidx] = qnode(u, qhead[v], id);
    qhead[v] = qidx++;
}

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 = qhead[u]; it != 0; it = qedges[it].next) {
        int v = qedges[it].to;
        if (vis[v])
            lca[qedges[it].idx] = findRoot(v);
    }
    for (int it = head[u]; it != 0; it = edges[it].next) {
        int v = edges[it].to;
        if (!vis[v]) {
            dis[v] = dis[u] + 1;
            tarjan(v);
            root[v] = u;
        }
    }
}

int query(int da, int ab, int ac, int bc)
{
    if (ab == ac)
        return da - dis[ab] + dis[bc] - dis[ab] + 1;
    else
        return da - max(dis[ab], dis[ac]) + 1;
}

int main()
{
    scanf("%d %d", &n, &q);
    range(i, 2, n)
    {
        scanf("%d", &v);
        addEdge(i, v);
    }
    each(i, q)
    {
        scanf("%d %d %d", a + i, b + i, c + i);
        addQEdge(a[i], b[i], i * 3);
        addQEdge(a[i], c[i], i * 3 + 1);
        addQEdge(b[i], c[i], i * 3 + 2);
    }
    tarjan(1);
    q *= 3;
    for (int i = 0; i < q; i += 3) {
        int al = query(dis[a[i / 3]], lca[i], lca[i + 1], lca[i + 2]);
        int bl = query(dis[b[i / 3]], lca[i + 2], lca[i], lca[i + 1]);
        int cl = query(dis[c[i / 3]], lca[i + 1], lca[i + 2], lca[i]);
        printf("%d\n", max(al, max(bl, cl)));
    }
    return 0;
}
LCA

LCA专题

Posted on

本文起始请听我先说一句

~~***的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) 的 时间和空间,但据我目前所知,只能单独对求两个点的距离没什么影响,如果略有变化。这样的写法就会出现错误 (比如第三道……) 所以我个人还是推荐使用建立有向边,再自行找出根节点的方法。
LCA

算法学习————LCA问题的Tarjan算法

Posted on

LCA 即 最近公共祖先

对于一棵有根树,就会有父亲结点,祖先结点。

     0
     |
     1
    /  \  
  2    3
       /  \
     4    5

举几个例子 如图 这棵树的所有节点的根节点都是 0
但是
4 5 的LCA 是3
2 5的LCA 是1
1 3的LCA 是1

这里要介绍的 求最近公共祖先的算法是 Tarjan 算法 算法的核心思想在于 我们从一棵树的根节点开始向下深搜 当我们回溯的时候 我们才把两个集合合并 并更新根节点

这就意味着 对于一个节点 我们只有访问过他的所有子节点和他本身之后才更新他的根节点 我再简单点说 这样操作就实现了从叶子节点不断向上更新根节点 如果我们再更新之前完成记录LCA的操作 一切并迎刃而解

附上伪代码

//parent为并查集,FIND为并查集的查找操作  
//QUERY为询问结点对集合  
//TREE为基图有根树  
Tarjan(u)  
    visit[u] = true  
        for each (u, v) in QUERY  
            if visit[v]  
                ans(u, v) = FIND(v)  
            for each (u, v) in TREE      
                if !visit[v]  
                    Tarjan(v)  
                parent[v] = u 

附上一个小题目 poj 1470

题意 多次查询后 问你LCA节点的次数

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int maxn=905;
struct node
{
    int v;
    node* nxt;
};
node* head1[maxn];
node* head2[maxn];
node edge1[maxn<<1],edge2[500005];
int root[maxn],num[maxn];
bool vis[maxn],flag[maxn];
int n,idx1,idx2,m;

void init()
{
    for(int i=0;i<=n;i++)
    {
        head1[i]=head2[i]=0;
        num[i]=vis[i]=flag[i]=0;
    }
    idx1=idx2=0;
}

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

void Tarjan(int u)
{
    root[u]=u;
    vis[u]=true;

    for(node* p=head2[u];p;p=p->nxt)
        if(vis[p->v])
            num[fin(p->v)]++;

    for(node* p=head1[u];p;p=p->nxt)
        if(!vis[p->v])
        {
            Tarjan(p->v);
            root[p->v]=u;
        }
}

void add(int u,int v,node* head[],node edge[],int& idx)
{
    edge[idx].v=v;
    edge[idx].nxt=head[u];
    head[u]=edge+idx++;

    edge[idx].v=u;
    edge[idx].nxt=head[v];
    head[v]=edge+idx++;
}

int main()
{
    int numm,u,v;
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d:(%d)",&u,&numm);
            while(numm--)
            {
                scanf(" %d",&v);
                flag[v]=true;
                add(u,v,head1,edge1,idx1);
            }
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf(" (%d %d)",&u,&v);
            add(u,v,head2,edge2,idx2);
        }
        for(int i=1;i<=n;i++)
            if(flag[i]==0)
            {
                Tarjan(i);
                break;
            }
        for(int i=1;i<=n;i++)
            if(num[i]) printf("%d:%d\n",i,num[i]);
    }
    return 0;
}
LCA

HDU 2874 Connections between cities

Posted on

换了个姿势还是上了HDU 据学长给我的图论题库来说 lca问题也写完了

这题几乎还是模板题 只不过是多了个 判断是否在同一棵树上 用了点小技巧 再Tarjan时 把根节点也传上去 如果得结果时根节点不同就跳过

另外这题灰常容易爆内存 稍微改了一下用 C++水过去了 然而G++还是爆………………

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int maxn=10005;
const int inf=0x3f3f3f3f;

struct node
{
    int v,d;
    node* nxt;
};

node *head1[maxn],edge1[maxn*2];
node *head2[maxn],edge2[2000002];
int root[maxn],ans[1000002],dis[maxn];
int vis[maxn];
int n,lnum,qnum,idx1,idx2;

void init()
{
    for(int i=0;i<=n;i++)
    {
        head1[i]=head2[i]=0;
        vis[i]=0;
    }
    idx1=idx2=0;
}

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

void add(int u,int v,int d,node *head[],node edge[],int& idx)
{
    edge[idx].v=v;
    edge[idx].d=d;
    edge[idx].nxt=head[u];
    head[u]=edge+idx++;

    edge[idx].v=u;
    edge[idx].d=d;
    edge[idx].nxt=head[v];
    head[v]=edge+idx++;
}

void Tarjan(int u,int rot)
{
    root[u]=u;
    vis[u]=rot;
    for(node* p=head2[u];p;p=p->nxt)
        if(vis[p->v]==rot)
            ans[p->d]=dis[u]+dis[p->v]-2*dis[fin(p->v)];
    for(node* p=head1[u];p;p=p->nxt)
        if(!vis[p->v])
        {
            dis[p->v]=dis[u]+p->d;
            Tarjan(p->v,rot);
            root[p->v]=u;
        }
}

int main()
{
    int u,v,d;
    while(scanf("%d%d%d",&n,&lnum,&qnum)!=EOF)
    {
        init();
        for(int i=1;i<=lnum;i++)
        {
            scanf("%d %d %d",&u,&v,&d);
            add(u,v,d,head1,edge1,idx1);
        }
        for(int i=1;i<=qnum;i++)
        {
            scanf("%d %d",&u,&v);
            ans[i]=inf;
            add(u,v,i,head2,edge2,idx2);
        }
        for(int i=1;i<=n;i++)
            if(!vis[i]) 
            {
                dis[i]=0;
                Tarjan(i,i);
            }
        for(int i=1;i<=qnum;i++)
        {
            if(ans[i]==inf) puts("Not connected");
            else printf("%d\n",ans[i]);
        }
    }
    return 0;
}