当前位置: 首页 > news >正文

CF1916G Optimizations From Chelsu

点分治,假设路径的端点是 \(s\)\(t\),那么 \(len\times g\) 就是 \((d_s+d_t)\times \gcd(v_s,v_t)\),其中 \(d\) 是到根链长度,\(v\) 是到根的 \(\gcd\)

不妨设 \(d_s\ge d_t\),那么 \((d_s+d_t)\times \gcd(v_s,v_t)\) 可能贡献到答案需要 \(>d_s\times v_s\),于是有 \(v_s\mid v_t\)

\(v_t=kv_s\)。上面的权值 \((d_s+d_t)\times v_s\) 还需要 \(>d_t\times v_t=kd_t\times v_s\),即 \(d_s>(k-1)d_t\)。那么有 \(k<\frac{d_s}{d_t}+1\le d_s+1\)

我们先统计所有端点为根的答案。然后对于每个 \(v_s\),找出其对应的最深的 \(s\)。如果 \(2d_s\times v_s\) 不超过当前答案就跳过。否则暴力枚举 \(k\) 统计答案。事实上我们可以说明,该做法复杂度为 \(O(n\log^2 n)\)


证明来自 洛谷题解。

考虑一次分治,设当前子树大小为 \(m\)

我们定义 \(u\) 为关键点当且仅当存在 \(k\),满足子树的深度(即子树内与 \(u\) 的最大距离)\(\ge 2^k\),且 \(u\) 的深度 \(=2^k\)

对于每个点 \(x\),找到其祖先中最深的关键点 \(u\),并将 \(x\) 放入 \(S(u,2^k,v_u)\)

首先根据定义,对于相同的 \(k\)\(S(u,2^k,g)\) 只有 \(O(\frac{m}{2^k})\) 个不为空。

对于每个不为空的集合,其中所有点 \(p\) 的深度都是 \(\le 2^{k+2}\) 的。因为我们去掉了不优于到根链的情况,所以此时 \(v_p>\frac{g}{4}\)。同时 \(v_p\) 需要是 \(v_u=g\) 的因数,所以合法的 \(v_p\) 只有 \(O(1)\) 个。我们只会对这 \(O(1)\) 个跑上面的暴力。

那么对于每个 \(k\),我们只会对 \(O(\frac{m}{2^k})\) 个点跑暴力,每次复杂度是 \(O(2^k)\) 的,因此单次复杂度 \(O(m)\)\(\log\) 层复杂度 \(O(m\log m)\)。同时点分治还会有一个 \(\log\),因此总复杂度 \(O(n\log^2 n)\)

代码里用了 map,复杂度多了一个 \(\log\)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int kN = 1e5 + 5;
int n;
ll ans;
vector<pair<int, ll>> g[kN];int siz[kN];
bool vis[kN];void DFS(int x, int fa) {siz[x] = 1;for(auto k : g[x]) {int to = k.first;if((to != fa) && !vis[to]) {DFS(to, x);siz[x] += siz[to];}}
}
int Root(int x, int fa, int all) {int mx = all - siz[x];for(auto k : g[x]) {int to = k.first;if((to != fa) && !vis[to]) {mx = max(mx, siz[to]);if(int tmp = Root(to, x, all)) {return tmp;}}}return (mx * 2 <= all) * x;
}struct Node {int mx, se, fr;Node() { mx = se = fr = 0; }Node(int _mx, int _se, int _fr) {mx = _mx;se = _se;fr = _fr;}
};
map<ll, Node> mp;void DFS2(int x, int fa, ll v, int d, int fr) {auto it = mp.lower_bound(v);if((it != mp.end()) && (it -> first == v)) {Node &info = it -> second;if(info.mx < d) {if(info.fr != fr) info.se = info.mx;info.mx = d;info.fr = fr;}else if(info.fr != fr) {info.se = max(info.se, d);}}else {mp.emplace_hint(it, v, Node(d, 0, fr));}for(auto k : g[x]) {int to; ll w;tie(to, w) = k;if((to != fa) && !vis[to]) DFS2(to, x, __gcd(v, w), d + 1, fr);}
}void Divide(int x) {DFS(x, 0);mp.clear();for(auto k : g[x]) {int to; ll w;tie(to, w) = k;if(!vis[to]) DFS2(to, x, w, 1, to);}for(auto k : mp) {ans = max(ans, k.first * k.second.mx);}for(auto k : mp) {ll val;Node info;tie(val, info) = k;if(2 * val * info.mx <= ans) continue;for(int i = 1; i <= info.mx; i++) {ll t = val * i;auto it = mp.find(t);if(it != mp.end()) {Node get = it -> second;if(get.fr != info.fr) {ans = max(ans, val * (info.mx + get.mx));}else {ans = max(ans, val * (info.mx + get.se));}}}}vis[x] = 1;for(auto k : g[x]) {int to = k.first;if(!vis[to]) Divide(Root(to, x, siz[to]));}
}void Solve() {cin >> n;fill_n(g, n + 3, vector<pair<int, ll>> {});fill_n(vis, n + 3, 0);for(int i = 1; i < n; i++) {int u, v; ll w;cin >> u >> v >> w;g[u].emplace_back(v, w);g[v].emplace_back(u, w);}ans = 0;DFS(1, 0), Divide(Root(1, 0, n));cout << ans << "\n";
}int main() {
//  freopen("1.in", "r", stdin);
//  freopen("1.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0);int t;cin >> t;while(t--) Solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=23803

相关文章:

  • 详细介绍:微服务架构:基于Spring Cloud ,构建同城生活服务平台
  • 云锵投资 2025 年 9 月简报
  • 【游记】北京师范大学讲课
  • 字符串Hash
  • 详细介绍:代码世界的“数字刑侦”:深入解析代码审计实战
  • 三霍尔BLDC如何测量Hall同步角度(需要示波器)
  • QBXT2025S刷题 Day2
  • PyCharm中搭建PyTorch和YOLOv10开发环境 - 实践
  • 基于PCIe(XDMA)的多路(1-32路)信号采集与回放子系统, 多路视频、AD、光纤等信号,支持PR over PCIe
  • Spring事务管理:@Transactional注解
  • AI元人文的未来:软硬件协同发展研究报告——声明Ai研究
  • 个人主页网址
  • 10.3考试t3(similarity)solution
  • 安卓渗透测试流
  • 日志|寻找旋转排序数组中的最小值|寻找两个正序数组的中位数|二分查找
  • 有关三角剖分的性质
  • 西门子通信-自制示意
  • Vue之刷新页面会触发的生命周期函数
  • 傅里叶的一生
  • Dos命令学习(新手)
  • 吴恩达深度学习课程一:神经网络和深度学习 第一周:深度学习简介
  • 实用指南:AI Agent开发平台如何设计?核心架构与工作流实战案例详解
  • Numercial result of HAA-DRSM
  • 防重复提交的实现
  • Day25错误(error)与异常(exception)的简单认识
  • 算法课第一次作业
  • 1. 对拍板子
  • Luogu P14122 [SCCPC 2021] Direction Setting题解 最小费用流
  • MySQL_基础
  • 5 qoj14553 序列与整数对 题解