四糸智乃

题解

算法(12)

/ 注册

全部文章 / 题解（共2篇）

2019CEOI D1T2 Dynamic Diameter

题目大意：给一颗无根带边权树。支持两种操作： 1、修改某条边的边权。 2、查询当前直径。点分树模板题，全局开一个multiset维护直径，对于每个重心开一颗线段树和一个局部multiset，用欧拉序线段树维护每一个子树中的最值，然后将其放入局部multiset。接下来取局部mul...

线段树点分树树分治树的直径 stl

2019-07-28

0 1124

CodeForces1019E Raining season

半平面交对偶转凸包树分治归并排序求闵可夫斯基和用李超线段树维护答案。题意：给一颗树，每条边的边权是一个关于t的一次函数，问你在每个t下树的直径是多少。如果t是定值，那么就是求直径。求直径的方法除了dfs两遍，还有一个方法是树分治，类似分治法求最大子段和。考虑树分治，找到重...

单调栈凸包树分治半平面交闵可夫斯基和李超树

2019-07-23

2 1501