Source and Judge
Noi2013
bzoj3242
Record
2h
Analysis
第一次写基环树(以前总觉得好麻烦啊不想写什么的……)
这次写是没事干练练码力
如果是一棵树,那么一定是找直径的中点
但在基环树上,直径的许多性质被破坏了,不能直接求图的直径
考虑把基环树转化为树,首先断掉一条边不会使答案更优,而且一定有一条边去掉不会有影响(考虑对最优点到各个点的路径一定是树)
把环拉成序列,然后答案的下界是max 各个树内直径/2,而且断边不会影响这个,先处理好,最后更新ans
然后设我们枚举的断边,右边的节点编号为k=1~cnt-1(从0开始)
然后分情况讨论直径经过环上边的情况,是在断边左边a、右边c或者从右边开始去往左边b
$$
\begin{aligned}
val是挂在这上面的树的最大深度,d是前缀环上距离\
A1(i)=&前缀max的val-d\
B1(i)=&后缀max的val-d\
B2(i)=&后缀max的val+d\
0<i<k,a=&A1(i-1)+d_i+val_i\
0 \leq i<k,b=&B1(k)+d_i+d_{cnt-1}+d_{cnt-1到0}+val_i\
k \leq i<cnt,c=&B2(i+1)-d_i+val_i\
ans=&min(ans,max(a,b,c))
\end{aligned}
$$
那么显然可以 O(n) 做了
|
|