最近公共祖先

最近公共祖先，树上两个点都能到达的，距离这两个点的距离和最近的一个点。也经常用LCA求树上两点间的距离。

在线的倍增法O(nlogn)：

POJ 1330 Nearest Common Ancestors

模板题， 求树上两个点的LCA

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int maxn = 10000 + 5;
const int DEG = 20;

struct edge {
    int to, nxt;
} e[maxn << 1];

int head[maxn], tot;

void addedge(int u, int v) {
    e[tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot++;
}

void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}

int fa[maxn][DEG];
int deg[maxn];

void bfs(int root) {
    queue<int> q;
    deg[root] = 0;
    fa[root][0] = root;
    q.push(root);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 1; i < DEG; i++)
            fa[u][i] = fa[fa[u][i-1]][i-1];
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].to;
            if (v == fa[u][0]) continue;
            deg[v] = deg[u] + 1;
            fa[v][0] = u;
            q.push(v);
        }
    }
}

int lca(int u, int v) {
    if (deg[u] > deg[v]) swap(u, v);
    int hu = deg[u], hv = deg[v];
    int tu = u, tv = v;
    for (int det = hv - hu, i = 0; det; det >>= 1, i++)
        if (det & 1) tv = fa[tv][i];
    if (tu == tv) return tu;
    for (int i = DEG - 1; i >= 0; i--) {
        if (fa[tu][i] == fa[tv][i]) continue;
        tu = fa[tu][i];
        tv = fa[tv][i];
    }
    return fa[tu][0];
}

int in[maxn];

int main() {
    //freopen("in.txt", "r", stdin);
    int t, n, u, v;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        init();
        memset(in, 0, sizeof(in));
        for (int i = 1; i < n; i++) {
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
            in[v]++;
        }
        for (int i = 1; i <= n; i++) {
            if (!in[i]) {
                bfs(i);
                break;
            }
        }
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));
    }
    return 0;
}

CDOJ 92 Journey

给出一棵有边权的树，再加上一条边，之后Q组询问，每次求两点之间的最短距离缩短了多少
添加一条边CD之后，原A，B间的最短路的走法可能变为 A-C-D-B 或者 A-D-B-C，和原来的A-B减一下就行了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100000 + 5;
const int DEP = 20;

struct edge {
    int to, nxt, cost;
} e[MAXN << 1];

int head[MAXN], tot;

void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}

void addedge(int u, int v, int w) {
    e[tot].to = v;
    e[tot].cost = w;
    e[tot].nxt = head[u];
    head[u] = tot++;
}

int fa[MAXN][DEP];
int dep[MAXN], dis[MAXN], n;

void dfs(int u, int pre, int d) {
    fa[u][0] = pre;
    dep[u] = d;
    for (int i = head[u]; i != -1; i = e[i].nxt) {
        int v = e[i].to;
        if (v == pre) continue;
        dis[v] = dis[u] + e[i].cost;
        dfs(v, u, d + 1);
    }
}

void initlca(int root) {
    dis[root] = 0;
    dfs(root, -1, 0);
    for (int i = 1; i < DEP; i++) {
        for (int u = 1; u <= n; u++) {
            if (fa[u][i-1] == -1) fa[u][i] = u;
            else fa[u][i] = fa[fa[u][i-1]][i-1];
        }
    }
}

int lca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    int hu = dep[u], hv = dep[v];
    int tu = u, tv = v;
    for (int det = hv - hu, i = 0; det; det >>= 1, i++)
        if (det & 1) tv = fa[tv][i];
    if (tu == tv) return tu;
    for (int i = DEP - 1; i >= 0; i--) {
        if (fa[tu][i] == fa[tv][i]) continue;
        tu = fa[tu][i];
        tv = fa[tv][i];
    }
    return fa[tu][0];
}

int main() {
    //freopen("in.txt", "r", stdin);
    int t, u, v, w, q;
    scanf("%d", &t);
    for (int _ = 1; _ <= t; _++) {
        printf("Case #%d:\n", _);
        scanf("%d%d", &n, &q);
        init();
        for (int i = 1; i < n; i++) {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        initlca(1);
        scanf("%d%d%d", &u, &v, &w);
        while (q--) {
            int a, b;
            scanf("%d%d", &a, &b);
            int L1 = dis[a] + dis[b] - 2 * dis[lca(a, b)];

            int L2 = dis[a] + dis[u] - 2 * dis[lca(a, u)]
            + dis[b] + dis[v] - 2 * dis[lca(b, v)] + w;

            int L3 = dis[a] + dis[v] - 2 * dis[lca(a, v)]
            + dis[b] + dis[u] - 2 * dis[lca(b, u)] + w;
            printf("%d\n", L1 - min(L1, min(L2, L3)));
        }
    }
    return 0;
}