• 2024-09-09CF1192B/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)}