我写的树上差分模板TLE了,怎么回事呢
  • 板块学术版
  • 楼主Sukilin
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/12 12:32
  • 上次更新2024/11/12 17:14:25
查看原帖
我写的树上差分模板TLE了,怎么回事呢
959201
Sukilin楼主2024/11/12 12:32
#include <iostream>
#include <cstdio>
const int N = 5e4 + 7;
const int J = 30;
int n;
int head[N], nex[N << 1], to[N << 1];
int cnt;
void add(int u, int v) {
    ++cnt;
    nex[cnt] = head[u];
    to[cnt] = v;
    head[u] = cnt;
}
int logn[N];
int fa[J][N], dep[N];
int init(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[0][u] = f;
    for (int i = 1; i <= logn[dep[u]]; i++) fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (int i = head[u]; i; i = nex[i])
        if (to[i] != f)
            init(to[i], u);
}
int lca(int u, int v) {
    if (dep[u] > dep[v])
        std::swap(u, v);
    for (int i = logn[dep[v]]; i >= 0; i--)
        if (dep[fa[i][v]] >= dep[u])
            v = fa[i][v];
    if (u == v)
        return v;
    for (int i = logn[dep[v]]; i >= 0; i--)
        if (fa[i][u] != fa[i][v])
            u = fa[i][u], v = fa[i][v];
    return fa[0][u];
}
int k;
int wei[N], d[N];
void maintain(int u, int v) {
    int l = lca(u, v);
    int fl = fa[0][l];
    ++d[u];
    --d[l];
    ++d[v];
    --d[fl];
}
int ans;
void dfs(int u, int f) {
    for (int i = head[u]; i; i = nex[i])
        if (to[i] != f)
            dfs(to[i], u), d[u] += d[to[i]];
    ans = std::max(ans, d[u]);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    logn[1] = 0;
    std::cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        add(u, v);
        add(v, u);
        logn[i + 1] = logn[(i + 1) << 1] + 1;
    }
    init(1, 0);
    for (int i = 1; i <= k; i++) {
        int s, t;
        std::cin >> s >> t;
        maintain(s, t);
    }
    dfs(1, 0);
    std::cout << ans << '\n';
    return 0;
}
2024/11/12 12:32
加载中...