Author: lllyouo
Date: 20250325
tag: 最近公共祖先、树上差分
link: https://www.luogu.com.cn/problem/P3128

问题描述

link

分析

略

参考代码

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

const int N = 50010, M = 1e5 + 10;
int h[N], e[M], ne[M], idx;
int f[N][20], d[N], b[N], sum[N];
int n, m, ans;

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

void bfs() {
    queue<int> q;
    q.push(1);
    d[1] = 1;

    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = h[x]; i != -1; i = ne[i]) {
            int y = e[i];
            if (d[y]) continue;
            d[y] = d[x] + 1;
            f[y][0] = x;

            int t = (int)(log(n) / log(2)) + 1;
            for (int j = 1; j <= t; j++) {
                f[y][j] = f[f[y][j - 1]][j - 1];
            }
            q.push(y);
        }
    }
}

int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);

    int t = (int)(log(n) / log(2)) + 1;
    for (int i = t; i >= 0; i--) {
        if (d[f[y][i]] >= d[x]) y = f[y][i];
    }
    if (x == y) return x;

    for (int i = t; i >= 0; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }

    return f[x][0];
}

void dfs(int u, int fa) {
    sum[u] = b[u];
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j != fa) {
            dfs(j , u);
            sum[u] += sum[j];
        }
    }

    ans = max(ans, sum[u]);
}

int main() {
    memset(h, -1, sizeof h);

    cin >> n >> m;
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    bfs();

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        int p = lca(a, b);
        b[a]++;
        b[b]++;
        b[f[p][0]]--;
        b[p]--;
    }

    dfs(1, -1);
    cout << ans << endl;

    return 0;
}