Link

Sol

karls图论题单里的绿题决定来水一水

我觉得完全可以树剖水过去。但是塔门说,让我讲讲树上差分。我说,“这不是一句话了事的事嘛。”所以我写了树上差分。

这个题是点差分,你就是在$w[u] + 1, w[v]+1,w[lca]-1,w[fa[lca]]-1$就可以了

如果是边查分,$w[u]+1,w[v]+1,w[lca]-2$

会了没有,回答的时候遍历一下记一下最大值了事。

Code

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

const int SIZE = 5e4 + 5;

int n, k, num, ind, ans;
int head[SIZE], w[SIZE], dfn[SIZE], f[SIZE][21];

struct node {
    int to, nxt; 
} edge[SIZE << 1];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

void addEdge(int u, int v) {
    edge[++ num].to = v, edge[num].nxt = head[u];
    head[u] = num;
}

void dfs(int u, int fa) {
    dfn[u] = ++ ind;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == fa) continue;
        f[v][0] = u;
        for (int j = 1; j <= 20; ++ j) f[v][j] = f[f[v][j - 1]][j - 1];
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (dfn[u] > dfn[v]) std::swap(u, v);
    if (u == v) return u;
    for (int i = 20; ~i; -- i) {
        if (dfn[f[v][i]] > dfn[u]) v = f[v][i];
    }
    return f[v][0];
}

void modify(int u, int v) {
    int fa = lca(u, v);
    ++ w[u], ++ w[v], -- w[fa], -- w[f[fa][0]];
}

int query(int u, int fa) {
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == fa) continue;
        query(v, u);
        w[u] += w[v];
    }
    ans = std::max(w[u], ans);
}

int main() {
    // freopen("code.in", "r", stdin);
    n = read(), k = read();
    for (int i = 1, u, v; i < n; ++ i) {
        u = read(), v = read();
        addEdge(u, v); addEdge(v, u);
    }
    dfs(1, 0);
    int u, v;
    while (k --) {
        u = read(), v = read();
        modify(u, v);
    }
    query(1, 0);
    printf("%d\n", ans);
    return 0;
}
最后修改:2021 年 09 月 04 日
如果觉得我的文章对你有用,请随意赞赏