acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 资讯
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 树上差分题解

    用个深搜

    userId_undefined
    复仇者_纳西妲厨一位
    时空双修者题解仙人秩序白银
    99阅读
    8回复
    3点赞
  • .

    #include <bits/stdc++.h> using namespace std; int n, k, ans, st[1000005][25], dep[1000005], diff[1000005], val[1000005]; vector <int> g[1000005]; void init(int u, int fa) { dep[u] = dep[fa] + 1; st[u][0] = fa; for (int i = 1; i <= 20; i++) st[u][i] = st[st[u][i - 1]][i - 1]; for(int v : g[u]) if (v != fa) init(v, u); } int LCA(int x, int y) { if (dep[x] < dep[y]) swap(x, y); int dis = dep[x] - dep[y]; for (int i = 0; i <= 20; i++) if ((dis >> i) & 1) x = st[x][i]; if (x == y) return x; for (int i = 20; i >= 0; i--) if (st[x][i] != st[y][i]) x = st[x][i], y = st[y][i]; return st[x][0]; } void dfs(int u, int fa) { val[u] = diff[u]; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); val[u] += val[v]; } ans = max(ans, val[u]); } int main() { for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } init(1, 0); while (k--) { int u, v; cin >> u >> v; int lca = LCA(u, v); diff[u] += 1, diff[v] += 1, diff[lca] -= 1, diff[st[lca][0]] -= 1; } dfs(1, 0); cout << ans; return 0; }

    userId_undefined
    王宇昊(威龙)
    时间刺客空间掌握者时空双修者循环·循环打卡人倔强青铜分支·分支解题者
    4阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页