斯坦纳树

不看 $c9$ I didn't even know there was such a thing.It is true that the food has reached a certain level.

目标是,In an undirected graph with nonnegative edge weights,Select the connected subgraph with the minimum edge weight and minimum,使得 $k$ a given point in the graph.Obviously only trees will be selected,Trees have roots.于是可以 $\mathtt{dp}$,记 $f(x,S)$ 为 $x$ Connect the rooted tree $S$ The minimum cost of keypoints within .

The root has only one son $f(x,S)\leftarrow f(y,S)+w(x,y)$,There are multiple sons $f(x,S)\leftarrow f(x,T)+f(x,S\setminus T)(T\ne \varnothing ,T⫋S)$ .

转移顺序,Obviously follow $|S|$ 升序.或者按照 $S$ 升序,in the binary value sense.Then it is easy to do the second type of transfer,Subset enumeration.

The first type of transition is the shortest-path transition,可以直接 $\text{dijkstra}$ 等.

Card often：应让 $S$ is the first dimension of the array,In this way, the memory access in the shortest time is very continuous.同时,The second type of transfer should also be enumerated first $T$ 再枚举 $i$ .

最小直径生成树

Enumerates the midpoint of the diameter,Then the answer is its furthest distance to all points multiplied by it $2$ .If that's not the midpoint,The value is too large.

So just find the midpoint of the graph,i.e. minimize its furthest distance to all points.

Find the shortest path to all sources,Then find the best point on each edge.是个 $\mathcal{O}(n)$ Piecewise function,每段的 $\min$ 易求.复杂度 $\mathcal{O}(nm)$ .

最小树形图

目标是,on a weighted directed graph,Find the subgraph that satisfies the edge weights and the smallest sum $r$ There is a unique path to each point（That is, a tree diagram）.It doesn't matter whether the frontier rights are non-negative or not,Because adding big positive numbers to all sides is enough.

Because it is more like a minimum spanning tree,所以可以贪心.有点不自然？But the logic is relatively strict.This is called the Zhu Liu algorithm.

The dendrogram is equivalent to giving except $r$ Each point of , selects the incoming edge,Make the graph acyclic.因此,给 $r$ Points other than the least weighted edge are selected,If this can form a treemap,That must be the best solution.

否则（There is an optimal solution such that ）There must be exactly one edge on the ring not selected.Because one side is not selected,Description cannot be adjusted,Shows that the points on both sides have the opposite reachability relation to this edge;Uncheck if there are at least two edges on the ring,A circular reachability relationship can be derived,矛盾.

So the ring can be reduced to a single point,The outside-to-inward edge becomes to replace the original incoming edge,That is, the edge weight of the original incoming edge is subtracted.This new single point also selects only one incoming edge,i.e. replace an edge,符合预期.

At least one point can be reduced per round（Not all points are in the ring,There may be only two points in the loop,The rest of the points form a dendrogram）,总复杂度 $\mathcal{O}(nm)$,The actual operation should run unsatisfactory.

还有个 $\text{tarjan}$ 算法.Make all points oriented $r$ 的连边,边权为 $+\infty$,It is not difficult to verify that this process is correct：维护一个栈,Initially there are arbitrary points in it $a$,Remove the top of the stack and its smallest incoming edge each time,Select the incoming edge.If the selected incoming edges form a ring,Apparently some points at the top of the stack,缩点（The new point remains on top of the stack）,Continue this process until only one point remains in the entire graph.

Use union search to deal with shrink points,Use can be stacked（带标记）It is enough to maintain the entry edge of each point.复杂度 $\mathcal{O}(m\log m)$ .

Comment. 奶奶滴,Why I figured out the complexity and $\text{OI-wiki}$ It's written differently