网站首页
编程语言
数据库
系统相关
其他分享
编程问答
CF1192B
2024-09-09
CF1192B/P6845 Dynamic Diameter
题意给定一棵带权树和\(q\)次询问,每次询问修改一条树边的权值,并查询修改后树的直径。询问之间不独立。\(n,q\le10^5\),强制在线。分析回想一下,两个点的距离可以被表示成\(dep_x+dep_y-2dep_{lca(x,y)}\)。而树的直径,本质上就是求\(\max_{x,y}dep_x+dep_y-2dep_{lca(x,y)}