Link-cut Trees

Blocking flows make a tree because of O(logU). However, this is dynamic trees, so you can delete and insert nodes. There is no direction basically.

This is the algorithm.

initially, makeTree() n times
while(true):
v = findRoot(s)
if (v == t)
//(z,parent(z)) is a min capacity edge with weight x
(z,x) = findMin(s)
subtract(s,x)
cut(z)
delete(z,parent(z)) from the level graph
continue
else
//try to advance
if v has an outgoing edge to some w in L:
link((v,w),capacity(v,w))
else
if (v == s): break
else for every child y of v
cut(y)
delete(y,v) from L

The cost of splaying nodes is O(logU). The total number of preferred child changes is O(m logU).