例题

最近公共祖先

$f[i][j]$ 表示$i$往上的第$2^j$个祖先的节点
$Log[i]$ 表示$log_2i$的整数部分
$dep[i]$ 表示$i$的深度

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 500500, M = 32;

int n, m, s;
int f[N][M], dep[N], Log[N];
int e[N << 1], ne[N << 1], h[N], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    f[u][0] = fa; // u的第一个祖宗节点就是它的父亲

    for (int i = 1; i <= Log[dep[u]]; i ++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    // u的第2^(i - 1)个祖宗节点的第2^(i - 1)个祖宗节点就是u的第2^i个祖宗节点
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != fa) dfs(j, u);
    }
}

int LCA(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    // 保证x是更深的那个节点
    while (dep[x] > dep[y]) x = f[x][Log[dep[x] - dep[y]]];
    // 一直让x跳,跳到与y同一层为止

    // 如果发现他们两个就在同一点上了,直接返回就行
    if (x == y) return x;
    // 这里让x,y同时跳,跳到父节点是同一节点为止(保证父节点是初始x和y的LCA)
    for (int i = Log[dep[x]]; i >= 0; i --)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

int main()
{
    scanf ("%d %d %d", &n, &m, &s);

    Log[0] = -1;
    for (int i = 1; i <= n; i ++)
        Log[i] = Log[i >> 1] + 1;

    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++)
    {
        int x, y;
        scanf ("%d %d", &x, &y);
        add(x, y);
        add(y, x);
    }

    dfs(s, 0);

    while (m --)
    {
        int a, b;
        scanf ("%d %d", &a, &b);
        printf ("%d\n", LCA(a, b));
    }

    return 0;
}

Max Flow P

考虑到需要对树上某个区间同时加上某个数,想到 树上差分

在操作时,给两个端点的差分值加$1$,再让它们的$LCA$差分值减去$1$,它们$LCA$的父节点差分值减去$1$

这样就实现了$x$到$LCA$到$y$的点的值都加上了$1$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 50050, M = 32;

int n, m, cnt[N], res;
int e[N << 2], ne[N << 2], h[N], idx;
int f[N][M], dep[N], Log[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;

    for (int i = 1; i <= Log[dep[u]]; i ++)
        f[u][i] = f[f[u][i - 1]][i - 1];

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j == fa) continue;
        dfs(j, u);
    }
}

int LCA(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);

    while (dep[x] > dep[y]) x = f[x][Log[dep[x] - dep[y]]];

    if (x == y) return x;

    for (int i = Log[dep[x]]; i >= 0; i --)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];

    return f[x][0];
}

void sum(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (j == fa) continue;

        sum(j, u);
        cnt[u] += cnt[j];
    }
    res = max(res, cnt[u]);
}

int main()
{
    scanf ("%d %d", &n, &m);

    Log[0] = -1;
    for (int i = 1; i <= n; i ++) Log[i] = Log[i >> 1] + 1;

    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++)
    {
        int a, b;
        scanf ("%d %d", &a, &b);
        add(a, b);
        add(b, a);
    }

    dfs(1, 0);

    while (m --)
    {
        int x, y;
        scanf ("%d %d", &x, &y);
        int lca = LCA(x, y);
        cnt[x] ++, cnt[y] ++, cnt[lca] --, cnt[f[lca][0]] --;
    }

    sum(1, 0); // 树上求一遍前缀和

    printf ("%d", res);
    return 0;
}

货车运输

首先,我们发现有些边是根本用不上的,比如1节点到3节点的最大限重是1,1-2是3,2-3是3,那1-3这条边我一定用不上
然后我们就可以利用最大生成树把这些边给删掉
然后我们可以运用LCA维护两个点到它们LCA的最小限重
最后求一遍两个点的LCA值就可以

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010, M = 50005, T = 32, INF = 0x3f3f3f3f;

int n, m, Q;
int f[N][T], res[N][T], dep[N], Log[N];
int e[M << 1], ne[M << 1], w[M << 1], h[N], idx;
int p[N];
bool st[N];
struct node
{
    int a, b, c;
    bool operator < (const node &E) const
    {
        return c > E.c;
    }
}edge[M];

int find(int x)
{
    if (p[x] != x) return p[x] = find(p[x]);
    return p[x];
}

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i], v = w[i];
        if (st[j]) continue;
        dep[j] = dep[u] + 1;
        f[j][0] = u;
        res[j][0] = v; // j到u的最小限重就是这个路径上的边权
        dfs(j);
    }
}

int LCA(int x, int y)
{
    if (find(x) != find(y)) return -1; // 如果两个点都不连通就是说明肯定走不到

    int ans = INF;
    if (dep[x] < dep[y]) swap(x, y);

    while (dep[x] > dep[y])
    {
        // 要先更新ans再更新x
        ans = min(ans, res[x][Log[dep[x] - dep[y]]]);
        x = f[x][Log[dep[x] - dep[y]]];
    }

    if (x == y) return ans;

    for (int i = Log[dep[x]]; i >= 0; i --)
        if (f[x][i] != f[y][i])
        {
            ans = min({ans, res[x][i], res[y][i]});
            x = f[x][i];
            y = f[y][i];
        }
    // 最后一步也要求一遍最小值
    // x,y此时虽然父节点是相同的,但到父节点的路径不一定相同,所以两个都需要求
    ans = min({ans, res[x][0], res[y][0]});
    return ans;
}

int main()
{
    scanf ("%d %d", &n, &m);

    Log[0] = -1;
    for (int i = 1; i <= n; i ++) Log[i] = Log[i >> 1] + 1;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++) p[i] = i;
    // 求最大生成树
    for (int i = 1; i <= m; i ++) scanf ("%d %d %d", &edge[i].a, &edge[i].b, &edge[i].c);

    sort(edge + 1, edge + m + 1);
    for (int i = 1; i <= m; i ++)
    {
        int a = edge[i].a, b = edge[i].b, c = edge[i].c;
        if (find(a) != find(b))
        {
            p[find(b)] = find(a);
            // 这个时候我们再建边
            add(a, b, c);
            add(b, a, c);
        }
    }
    // 这里我要遍历每一个点,因为可能有多个连通块
    for (int i = 1; i <= n; i ++)
        if (!st[i])
        {
            dep[i] = 1; // 自己就是根
            f[i][0] = i;
            res[i][0] = INF; // 一定要赋成正无穷
            dfs(i); // 这个题教会我dfs不用传fa的值也可以维护LCA
        }
    // 在所有的f[i][0],w[i][0]都求出后,我们再继续维护
    for (int i = 1; i < T; i ++)
        for (int j = 1; j <= n; j ++)
        {
            f[j][i] = f[f[j][i - 1]][i - 1];
            // 我觉得这句话还是要好好理解的
            // 从 j 到 j的2^j个父节点 的最小限重是下面的最小值
            // j 到 j的2^(i - 1)个父节点 路径上的最小限重 
            // j的2^(i - 1)个父节点 到 j的2^i个父节点 路径上的最小限重
            res[j][i] = min(res[f[j][i - 1]][i - 1], res[j][i - 1]);
        }

    scanf ("%d", &Q);

    while (Q --)
    {
        int x, y;
        scanf ("%d %d", &x, &y);
        printf ("%d\n", LCA(x, y));
    }
    return 0;
}