[一本通学习笔记] 最近公共祖先LCA

本节内容过于暴力没什么好说的。借着这个专题改掉写倍增的陋习，虽然写链剖代码长了点不过常数小还是很香。

10130. 「一本通 4.4 例 1」点的距离

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

const int N = 1000005;

namespace tree {
int n;
vector<int> g[N];
int top[N], wson[N], dep[N], siz[N], vis[N], fa[N], dfn[N], idfn[N], ind;

void read() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void dfs1(int p) {
    vis[p] = 1;
    siz[p] = 1;
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i];
        if (vis[q])
            continue;
        fa[q] = p;
        dep[q] = dep[p] + 1;
        dfs1(q);
        siz[p] += siz[q];
        if (siz[q] > siz[wson[p]])
            wson[p] = q;
    }
}

void dfs2(int p) {
    vis[p] = 1;
    dfn[p] = ++ind;
    idfn[ind] = p;
    if (wson[p]) {
        top[wson[p]] = top[p];
        dfs2(wson[p]);
    }
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i];
        if (vis[q])
            continue;
        top[q] = q;
        dfs2(q);
    }
}

void presolve() {
    memset(vis, 0, sizeof vis);
    dfs1(1);
    memset(vis, 0, sizeof vis);
    top[1] = 1;
    dfs2(1);
}

int lca(int p, int q) {
    while (top[p] != top[q]) {
        if (dep[top[p]] > dep[top[q]])
            swap(p, q);
        q = fa[top[q]];
    }
    if (dep[p] > dep[q])
        swap(p, q);
    return p;
}
}  // namespace tree

int main() {
    ios::sync_with_stdio(false);
    tree::read();
    tree::presolve();
    int q, t1, t2;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> t1 >> t2;
        cout << tree::dep[t1] + tree::dep[t2] - 2 * tree::dep[tree::lca(t1, t2)] << endl;
    }
}

10131. 「一本通 4.4 例 2」暗的连锁

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

int n, m, u, v, ind;
const int N = 1000005;
int fa[N], dep[N], siz[N], wson[N], top[N], dfn[N], idfn[N], vis[N], sum[N];
vector<int> g[N];
long long ans = 0;
void dfs1(int p) {
    vis[p] = 1;
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i];
        if (vis[q])
            continue;
        fa[q] = p;
        dep[q] = dep[p] + 1;
        dfs1(q);
        if (siz[q] > siz[wson[p]])
            wson[p] = q;
        siz[p] += siz[q];
    }
}

void dfs2(int p) {
    vis[p] = 1;
    dfn[p] = ++ind;
    idfn[ind] = p;
    if (wson[p]) {
        top[wson[p]] = top[p];
        dfs2(wson[p]);
    }
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i];
        if (vis[q])
            continue;
        top[q] = q;
        dfs2(q);
    }
}

int lca(int p, int q) {
    while (top[p] != top[q]) {
        if (dep[top[q]] > dep[top[p]])
            swap(p, q);
        p = fa[top[p]];
    }
    if (dep[q] > dep[p])
        swap(p, q);
    return q;
}

void dfs3(int p) {
    vis[p] = 1;
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i];
        if (vis[q])
            continue;
        dfs3(q);
        sum[p] += sum[q];
    }
    ans += (sum[p] == 1 ? 1 : 0) + (sum[p] == 0 ? m * (p > 1) : 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1);
    memset(vis, 0, sizeof vis);
    top[1] = 1;
    dfs2(1);
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        sum[u]++;
        sum[v]++;
        sum[lca(u, v)] -= 2;
    }
    memset(vis, 0, sizeof vis);
    dfs3(1);
    cout << ans << endl;
}

10132. 「一本通 4.4 例 3」异象石

这个题值得去思考一下。首先维护集合并对答案进行转化的方法值得借鉴（个人柑橘有种欧拉序的味道），然后是对集合边界的特殊处理需要注意。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, x, y, z, ind;
char op;
const int N = 1000005;
int fa[N], dep[N], dis[N], top[N], dfn[N], fin[N], idfn[N], vis[N], wson[N], siz[N];
vector<pair<int, int> > g[N];

void dfs1(int p) {
    vis[p] = 1;
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i].first;
        if (vis[q])
            continue;
        fa[q] = p;
        dep[q] = dep[p] + 1;
        dis[q] = dis[p] + g[p][i].second;
        dfs1(q);
        siz[p] += siz[q];
        if (siz[q] > siz[wson[p]])
            wson[p] = q;
    }
}
void dfs2(int p) {
    vis[p] = 1;
    dfn[p] = ++ind;
    idfn[ind] = p;
    if (wson[p]) {
        top[wson[p]] = top[p];
        dfs2(wson[p]);
    }
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i].first;
        if (vis[q])
            continue;
        top[q] = q;
        dfs2(q);
    }
    fin[p] = ++ind;
}
int lca(int p, int q) {
    while (top[p] != top[q]) {
        if (dep[top[p]] < dep[top[q]])
            swap(p, q);
        p = fa[top[p]];
    }
    if (dep[p] < dep[q])
        swap(p, q);
    return q;
}
int dist(int p, int q) {
    // cout<<"dis <"<<p<<","<<q<<"> = "<<dis[p]+dis[q]-2*dis[lca(p,q)]<<endl;
    return dis[p] + dis[q] - 2 * dis[lca(p, q)];
}
set<int> s;
long long ans = 0;
signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> x >> y >> z;
        g[x].push_back(make_pair(y, z));
        g[y].push_back(make_pair(x, z));
    }
    dfs1(1);
    memset(vis, 0, sizeof vis);
    top[1] = 1;
    dfs2(1);
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == '+') {
            cin >> x;
            set<int>::iterator pre, suf;
            if (s.size()) {
                pre = suf = s.lower_bound(dfn[x]);
                if (suf == s.end())
                    suf = s.begin();
                if (pre == s.begin())
                    pre = --s.end();
                else
                    --pre;
                int p = idfn[*pre], q = idfn[*suf];
                ans += dist(p, x) + dist(q, x) - dist(p, q);
            }
            s.insert(dfn[x]);
        }
        if (op == '-') {
            cin >> x;
            set<int>::iterator pre, suf;
            s.erase(dfn[x]);
            if (s.size()) {
                pre = suf = s.lower_bound(dfn[x]);
                if (suf == s.end())
                    suf = s.begin();
                if (pre == s.begin())
                    pre = --s.end();
                else
                    --pre;
                int p = idfn[*pre], q = idfn[*suf];
                ans -= dist(p, x) + dist(q, x) - dist(p, q);
            }
        }
        if (op == '?') {
            cout << ans / 2 << endl;
        }
        // cout<<ans<<endl;
    }
}

10133. 「一本通 4.4 例 4」次小生成树

我仍然没找到我91分的原因是什么

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;

struct Edge {
    int u, v, w;
    bool operator<(const Edge &b) { return w < b.w; }
};

int n, m, t1, t2, t3, t4;
Edge e[N];
bool f[N];  // 1 - on tree
vector<pair<int, int> > g[N];

namespace Kruskal {
int fa[N], ans;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int p, int q) {
    p = find(p);
    q = find(q);
    fa[p] = q;
}
void solve() {
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        if (find(e[i].u) != find(e[i].v)) {
            merge(e[i].u, e[i].v);
            ans += e[i].w;
            f[i] = true;
            g[e[i].u].push_back(make_pair(e[i].v, e[i].w));
            g[e[i].v].push_back(make_pair(e[i].u, e[i].w));
        }
    }
}
}  // namespace Kruskal

namespace SegmentTree {
int a[N << 2], b[N << 2];
void build(int p, int l, int r, int *src) {
    if (l == r)
        a[p] = src[l];
    else {
        build(p * 2, l, (l + r) / 2, src);
        build(p * 2 + 1, (l + r) / 2 + 1, r, src);
        a[p] = max(a[p * 2], a[p * 2 + 1]);
        if (a[p * 2] < a[p])
            b[p] = a[p * 2];
        else if (a[p * 2 + 1] < a[p])
            b[p] = a[p * 2 + 1];
        else
            b[p] = max(b[p * 2], b[p * 2 + 1]);
    }
}
int query(int p, int l, int r, int ql, int qr) {
    if (l > qr || r < ql)
        return 0;
    if (l >= ql && r <= qr)
        return a[p];
    return max(query(p * 2, l, (l + r) / 2, ql, qr), query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr));
}
int querys(int p, int l, int r, int ql, int qr) {
    if (l > qr || r < ql)
        return 0;
    if (l >= ql && r <= qr)
        return b[p];
    return max(querys(p * 2, l, (l + r) / 2, ql, qr), querys(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr));
}
}  // namespace SegmentTree

namespace Tree {
int ind, fa[N], siz[N], dep[N], dis[N], vis[N], wson[N], top[N], dfn[N];
void dfs1(int p) {
    vis[p] = 1;
    siz[p] = 1;
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i].first;
        if (vis[q])
            continue;
        dep[q] = dep[p] + 1;
        dis[q] = g[p][i].second;
        fa[q] = p;
        dfs1(q);
        siz[p] += siz[q];
        if (siz[wson[p]] < siz[q])
            wson[p] = q;
    }
}
void dfs2(int p) {
    vis[p] = 1;
    dfn[p] = ++ind;
    if (wson[p]) {
        top[wson[p]] = top[p];
        dfs2(wson[p]);
    }
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i].first;
        if (vis[q])
            continue;
        top[q] = q;
        dfs2(q);
    }
}
void presolve() {
    dfs1(1);
    memset(vis, 0, sizeof vis);
    top[1] = 1;
    dfs2(1);
}
int query(int p, int q) {
    int ret = 0;
    while (top[p] != top[q]) {
        if (dep[top[p]] < dep[top[q]])
            swap(p, q);
        ret = max(ret, SegmentTree::query(1, 1, n, dfn[top[p]], dfn[p]));
        p = fa[top[p]];
    }
    if (dep[p] > dep[q])
        swap(p, q);
    return max(ret, SegmentTree::query(1, 1, n, dfn[p] + 1, dfn[q]));
}
int querys(int p, int q) {
    int ret = 0, lim = query(p, q);
    while (top[p] != top[q]) {
        if (dep[top[p]] < dep[top[q]])
            swap(p, q);
        if (SegmentTree::query(1, 1, n, dfn[top[p]], dfn[p]) < lim)
            ret = max(ret, SegmentTree::query(1, 1, n, dfn[top[p]], dfn[p]));
        else
            ret = max(ret, SegmentTree::querys(1, 1, n, dfn[top[p]], dfn[p]));
        p = fa[top[p]];
    }
    if (dep[p] > dep[q])
        swap(p, q);
    if (SegmentTree::query(1, 1, n, dfn[p] + 1, dfn[q]) < lim)
        return max(ret, SegmentTree::query(1, 1, n, dfn[p] + 1, dfn[q]));
    else
        return max(ret, SegmentTree::querys(1, 1, n, dfn[p] + 1, dfn[q]));
}
}  // namespace Tree

int val[N];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        e[i].u = t1;
        e[i].v = t2;
        e[i].w = t3;
    }
    Kruskal::solve();
    Tree::presolve();
    for (int i = 1; i <= n; i++) {
        val[Tree::dfn[i]] = Tree::dis[i];
    }
    SegmentTree::build(1, 1, n, val);
    int ans = 1e+15;
    for (int i = 1; i <= m; i++) {
        // cout<<i<<", "<<f[i]<<", "<<e[i].w - Tree::query(e[i].u,e[i].v)<<endl;
        if (f[i] == false) {
            if (e[i].w - Tree::query(e[i].u, e[i].v))
                ans = min(ans, e[i].w - Tree::query(e[i].u, e[i].v));
            else
                ans = min(ans, e[i].w - Tree::querys(e[i].u, e[i].v));
        }
    }
    cout << ans + Kruskal::ans << endl;
}

10134. 「一本通 4.4 练习 1」Dis

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

int n, m, ind, t1, t2, t3;
const int N = 1000005;
int fa[N], vis[N], dis[N], dep[N], top[N], siz[N], wson[N], dfn[N];
vector<pair<int, int> > g[N];

void dfs1(int p) {
    vis[p] = 1;
    siz[p] = 1;
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i].first;
        if (vis[q])
            continue;
        fa[q] = p;
        dep[q] = dep[p] + 1;
        dis[q] = dis[p] + g[p][i].second;
        dfs1(q);
        siz[p] += siz[q];
        if (siz[q] > siz[wson[p]])
            wson[p] = q;
    }
}
void dfs2(int p) {
    vis[p] = 1;
    dfn[p] = ++ind;
    if (wson[p]) {
        top[wson[p]] = top[p];
        dfs2(wson[p]);
    }
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i].first;
        if (vis[q])
            continue;
        top[q] = q;
        dfs2(q);
    }
}

int lca(int p, int q) {
    while (top[p] != top[q]) {
        if (dep[top[p]] < dep[top[q]])
            swap(p, q);
        p = fa[top[p]];
    }
    if (dep[p] < dep[q])
        swap(p, q);
    return q;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        cin >> t1 >> t2 >> t3;
        g[t1].push_back(make_pair(t2, t3));
        g[t2].push_back(make_pair(t1, t3));
    }
    dfs1(1);
    memset(vis, 0, sizeof vis);
    top[1] = 1;
    dfs2(1);
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2;
        cout << dis[t1] + dis[t2] - 2 * dis[lca(t1, t2)] << endl;
    }
}

10135. 「一本通 4.4 练习 2」祖孙询问

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

const int N = 1000005;
int n, m, ind, t1, t2, t3, t4;
int vis[N], dep[N], siz[N], top[N], wson[N], dfn[N], fa[N];
vector<int> g[N];

void dfs1(int p) {
    vis[p] = 1;
    siz[p] = 1;
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i];
        if (vis[q])
            continue;
        fa[q] = p;
        dep[q] = dep[p] + 1;
        dfs1(q);
        siz[p] += siz[q];
        if (siz[wson[p]] < siz[q])
            wson[p] = q;
    }
}

void dfs2(int p) {
    vis[p] = 1;
    dfn[p] = ++ind;
    if (wson[p]) {
        top[wson[p]] = top[p];
        dfs2(wson[p]);
    }
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i];
        if (vis[q])
            continue;
        top[q] = q;
        dfs2(q);
    }
}

int lca(int p, int q) {
    while (top[p] != top[q]) {
        if (dep[top[p]] < dep[top[q]])
            swap(p, q);
        p = fa[top[p]];
    }
    if (dep[p] > dep[q])
        swap(p, q);
    return p;
}

map<int, int> mp;
int root;
int x[N], y[N], cnt, Index;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t1 >> t2;
        if (t2 == -1) {
            root = t1;
        } else {
            ++cnt;
            x[cnt] = t1;
            y[cnt] = t2;
            mp[t1]++;
            mp[t2]++;
        }
    }
    for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) {
        it->second = ++Index;
    }
    for (int i = 1; i <= cnt; i++) {
        x[i] = mp[x[i]];
        y[i] = mp[y[i]];
        g[x[i]].push_back(y[i]);
        g[y[i]].push_back(x[i]);
    }
    root = mp[root];
    dfs1(root);
    memset(vis, 0, sizeof vis);
    top[root] = root;
    dfs2(root);
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> t1 >> t2;
        t1 = mp[t1];
        t2 = mp[t2];
        int l = lca(t1, t2);
        if (l == t1 && l != t2)
            cout << 1 << endl;
        else if (l == t2 && l != t1)
            cout << 2 << endl;
        else
            cout << 0 << endl;
    }
}

10136. 「一本通 4.4 练习 3」聚会

分类以后总结一下发现就是最深的那个LCA

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

int n, m, t1, t2, t3, t4, ind;
const int N = 1000005;
int fa[N], dep[N], siz[N], vis[N], wson[N], top[N], dfn[N];
vector<int> g[N];
void dfs1(int p) {
    vis[p] = 1;
    siz[p] = 1;
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i];
        if (vis[q])
            continue;
        fa[q] = p;
        dep[q] = dep[p] + 1;
        dfs1(q);
        siz[p] += siz[q];
        if (siz[wson[p]] < siz[q])
            wson[p] = q;
    }
}
void dfs2(int p) {
    vis[p] = 1;
    dfn[p] = ++ind;
    if (wson[p]) {
        top[wson[p]] = top[p];
        dfs2(wson[p]);
    }
    for (int i = 0; i < g[p].size(); i++) {
        int q = g[p][i];
        if (vis[q])
            continue;
        top[q] = q;
        dfs2(q);
    }
}
int lca(int p, int q) {
    while (top[p] != top[q]) {
        if (dep[top[p]] < dep[top[q]])
            swap(p, q);
        p = fa[top[p]];
    }
    if (dep[p] < dep[q])
        swap(p, q);
    return q;
}
int dist(int p, int q) { return dep[p] + dep[q] - 2 * dep[lca(p, q)]; }

int main() {
    ios::sync_with_stdio(false);
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &t1, &t2);
        g[t1].push_back(t2);
        g[t2].push_back(t1);
    }
    dfs1(1);
    memset(vis, 0, sizeof vis);
    top[1] = 1;
    dfs2(1);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &t1, &t2, &t3);
        int l1 = lca(t1, t2), l2 = lca(t2, t3), l3 = lca(t3, t1);
        if (dep[l2] > dep[l1])
            l1 = l2;
        if (dep[l3] > dep[l1])
            l1 = l3;
        printf("%d %d\n", l1, dist(l1, t1) + dist(l1, t2) + dist(l1, t3));
    }
}