最近公共祖先

LCA（Least Common Ancestors），即最近公共祖先，指对于有根树 T 的两个结点 u 、v ，最近公共祖先 LCA(T,u,v) 表示一个结点 x, 满足 x 是 u、v 的祖先且 x 的深度尽可能大。

树上倍增

int anc[maxn][32]; // 结点 i 的第 2^j 个祖先
int depth[maxn];   // 深度
int dis[maxn];     // 距离

void dfs(int x, int fa, int d) {
    depth[x] = d;
    for(int i = head[x]; ~i; i = e[i].next) {
        int j = e[i].to;
        if (j == fa) continue;
        anc[j][0] = x;
        dis[j] = dis[x] + e[i].val;
        dfs(j, x, d+1);
    }
}

void init(int n) { // 预处理
    dfs(1, 0, 0);
    int m = 31 - __builtin_clz(n);
    for(int j = 1; j <= m; ++ j) {
        for(int i = 1; i <= n; ++ i) {
            anc[i][j] = anc[anc[i][j-1]][j-1];
        }
    }
}

int lca(int a, int b) { // 最近公共祖先
    if (depth[a] < depth[b]) swap(a,b);
    int h = depth[a] - depth[b];
    for(int i = 31-__builtin_clz(h); i >= 0; -- i) {
        if ((h>>i) & 1) a = anc[a][i];
    }
    if (a != b) {
        for(int i = 31-__builtin_clz(depth[b]); i >= 0; -- i) {
            if (anc[a][i] != anc[b][i]) {
                a = anc[a][i];
                b = anc[b][i];
            }
        }
        a = anc[a][0];
    }
    return a;
}

树链刨分

(https://acm.ecnu.edu.cn/contest/354/problem/A/)
#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e4+1;

struct node{
    int to, w, next;
}e[maxn<<1]; int head[maxn], tot;
void addedge(int x, int y, int val) {
    e[++tot] = {y, val, head[x]}, head[x] = tot;
    e[++tot] = {x, val, head[y]}, head[y] = tot;
}

int dis[maxn], depth[maxn];
int fa[maxn], siz[maxn], son[maxn];
void dfs1(int u,int f){
    fa[u]=f;
    depth[u] = depth[f] + 1;
    siz[u]=1;
    int maxsize=-1;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==f) continue;
        dis[v] = dis[u] + e[i].w;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>maxsize){
            maxsize=siz[v];
            son[u]=v;
        }
    }
}
int cnt, dfn[maxn], top[maxn];
void dfs2(int u,int t){
    dfn[u]=++cnt;
    top[u]=t;
    if(!son[u]) return ;
    dfs2(son[u],t);
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==fa[u]||v==son[u]) continue ;
        dfs2(v,v);
    }
}

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(depth[top[x]]<depth[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return depth[x]<depth[y]?x:y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    memset(head, -1, sizeof head);
    for(int i = 1; i < n; ++ i) {
        int x, y, z;
        cin >> x >> y >> z;
        addedge(x+1, y+1, z);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    int T;
    cin >> T;
    while(T --) {
        long long a[6], res = 0;
        cin >> a[1] >> a[2] >> a[3] >> a[4] >> a[5];
        a[1] ++, a[2] ++, a[3] ++, a[4] ++, a[5] ++;
        for(int i = 5; i >= 2; -- i) {
            int x = 1, y = 1, z = -1, t;
            for(int j = 1; j <= i; ++ j) {
                for(int k = j+1; k <= i; ++ k) {
                    int ro = LCA(a[j], a[k]);
                    if (z < depth[ro]) z = depth[ro], x = j, y = k, t = ro;
                }
            }
            res += dis[a[x]] + dis[a[y]] - 2*dis[t];
            if (y == i) swap(a[x], a[i-1]);
            else swap(a[x], a[i]), swap(a[y], a[i-1]);
            a[i-1] = t;
        }
        cout << res << "\n";
    }
    return 0;
}

专题

http://acm.hdu.edu.cn/showproblem.php?pid=2586 【入门】