最近公共祖先(LCA)、树上差分

最近公共祖先$\text{(LCA)}$：

给定一颗有根树，若节点$z$既是节点$x$的祖先，也是节点$y$的祖先，则称$z$是$x,y$的公共祖先。在$x,y$的所有公共祖先种，深度最大的一个称为最近公共祖先，记作$\text{LCA}(x,y)$

做法一：向上标记法

从$x$向上走到根节点，标记所有经过的节点，再从$y$向上走，当第一次遇到已标记的节点是，那么此节点就是$\text{LCA}(x,y)$

每个询问时间复杂度最坏$O(n)$

不推荐这种做法

做法二：树上倍增法

对路径做二进制拆分，每个数都能表示为$2$的幂次和。

设$F_{x,k}$表示$x$走$2^k(k\in [1,\log n])$到达的节点，若节点不存在$F_{x,k}=0$。

$2^k=2^{k-1}+2^{k-1}$，所以$F_{x,k}=F_{F_{x,k-1},k-1}$

用$\text{BFS}$预处理每个节点的深度$d_i$和$F_{x,k}$

具体步骤：

$1.$先找到深度最大的节点，假设为$x$

$2.$把$x$向上走到与$y$同一深度（一定可以跳到），也就是依次尝试从节点$x$向上走$k=2^{\log n},\cdots ,2^1,2^0$步，每次尝试$x=F_{x,k}$

$3.$如果$x=y$，那么此时$\text{LCA}(x,y)=x$，停止查找

$4.$否则，继续让$x$和$y$同时向上走$k=2^{\log n},\cdots ,2^1,2^0$步，每次尝试$x=F_{x,k},y=F_{y,k}$

$5.$最后$x$与$y$只差一步就可以相遇，那么此时$\text{LCA}(x,y)=F_{x,0}$

预处理时间复杂度$O(n\log n)$，每个询问时间复杂度$O(\log n)$

模板题：AcWing 1172 祖孙询问

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 4e4 + 5;
int n, Q, depth[N], fa[N][16], e[2 * N], h[N], ne[2 * N], idx, root, u, v;
void add(int a, int b) {
   
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs() {
   
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
   
        auto t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
   
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
   
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                for (int k = 1; k <= 15; k ++) fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}
int lca(int u, int v) {
   
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = 15; ~k; k --)
        if (depth[fa[u][k]] >= depth[v]) u = fa[u][k];
    if (u == v) return u;
    for (int k = 15; ~k; k --)
        if (fa[u][k] != fa[v][k]) u = fa[u][k], v = fa[v][k];
    return fa[u][0];
}
signed main() {
   
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n; i ++) {
   
        cin >> u >> v;
        if (v == -1) {
   
            root = u;
        } else {
   
            add(u, v), add(v, u);
        }
    }
    bfs();
    cin >> Q;
    while (Q --) {
   
        cin >> u >> v;
        int p = lca(u, v);
        if (p == u) {
   
            cout << 1 << endl;
        } else if (p == v) {
   
            cout << 2 << endl;
        } else {
   
            cout << 0 << endl;
        }
    }
}

做法三：$\text{tarjan}$

离线每个询问$q_i$。先做$\text{DFS}$，把每个点分为三类：当前正在访问的点标记为$1$，已经回溯过的点标记为$2$，还未被搜索的点标记为$0$，那么所有标记为$2$的点的$\text{LCA}$都对应标记为$1$的点的路径上的一个根节点，所以就可以用并查集维护，找到一个代表节点，作为$\text{LCA}$，搜索完该点之后维护一次并查集。

时间复杂度$O(n+m)$

模板题： AcWing 1171 距离

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, M = 2 * N;
int n, Q, u, v, c, h[N], ne[M], e[M], w[M] ,idx, p[N], st[N], ans[M], dist[N];
vector<int> query[M], query_id[M];
void add(int a, int b, int c) {
   
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int find(int x) {
   
    return p[x] == x ? p[x] : p[x] = find(p[x]);
}
void tarjan(int u) {
   
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
   
        int j = e[i];
        if (st[j]) continue;
        dist[j] = dist[u] + w[i];
        tarjan(j);
        p[j] = u;
    }
    for (int i = 0; i < query[u].size(); i ++) {
   
        int j = query[u][i], id = query_id[u][i];
        if (st[j] == 2) {
   
            int lca = find(j);
            ans[id] = dist[u] + dist[j] - 2 * dist[lca];
        }
    }
    st[u] = 2;
}
signed main() {
   
    memset(h, -1, sizeof h);
    cin >> n >> Q;
    for (int i = 1; i <= n; i ++) p[i] = i;
    for (int i = 0; i < n - 1; i ++) {
   
        cin >> u >> v >> c;
        add(u, v, c), add(v, u, c);
    }
    for (int i = 0; i < Q; i ++) {
   
        cin >> u >> v;
        if (u == v) {
   
            ans[i] = 0;
        } else {
   
            query[u].push_back(v), query[v].push_back(u);
            query_id[u].push_back(i), query_id[v].push_back(i);
        }
    }
    tarjan(1);
    for (int i = 0; i < Q; i ++) cout << ans[i] << endl;
}

树上差分：

对于两个点$x,y$想要在经过$x,y$的路径上都增加边权$c$，可以用树上差分来维护，做法：用$F_i$表示以$i$为根的字数各节点权值之和，每次操作将$F_x+c,F_y+c,F_{\text{LCA}(x,y)}-2c$，最后做一遍$\text{DFS}$进行前缀和，最后就得到了每条边的权值，和数组的差分前缀和思想差不多。

模板题：AcWing 352 闇の連鎖

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 2 * N;
int n, m, h[N], e[M], ne[M], idx, u, v, depth[N], cf[N], ans, fa[N][17];
void add(int a, int b) {
   
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs() {
   
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
   
        auto t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
   
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
   
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;
                for (int k = 1; k <= 16; k ++) {
   
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                }
            }
        }
    }
}
int lca(int a, int b) {
   
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 16; ~k; k --)
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 16; ~k; k --)
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}
int dfs(int u, int father) {
   
    int res = cf[u];
    for (int i = h[u]; ~i; i = ne[i]) {
   
        int j = e[i];
        if (j == father) continue;
        int s = dfs(j, u);
        if (!s) {
   
            ans += m;
        } else if (s == 1) {
   
            ans ++;
        }
        res += s;
    }
    return res;
}
signed main() {
   
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < n - 1; i ++) {
   
        cin >> u >> v;
        add(u, v), add(v, u);
    }
    bfs();
    for (int i = 0; i < m; i ++) {
   
        cin >> u >> v;
        cf[u] ++, cf[v] ++, cf[lca(u, v)] -= 2;
    }
    dfs(1, -1);
    cout << ans << endl;
}