I look for a simple algorithm for *parametric minimum spanning tree* where the weight of the edge e is $a\_e + \lambda b\_e $. Can we simplify the algorithm in case $b\_e=1$ for all edges?



Parametric minimum spanning tree
I don't know of any "simple" algorithms, but algorithms are known. See for example [Using Sparsification for Parametric Minimum Spanning Tree Problems](http://web.cs.iastate.edu/~fernande/PAPERS/sparsif.pdf) or [Parametric and Kinetic Minimum Spanning Trees](https://www.ics.uci.edu/~eppstein/pubs/AgaEppGui-FOCS-98.pdf).


If we assume $b\_e = 1$ for all edges, then the situation does simplify. In this case it is just the usual minimum spanning tree problem with weights $a\_e$ only. For a graph with $n$ vertices any spanning tree will have exactly $n-1$ edges. So, for any $\lambda \in \mathbb{R}$ the weight of any spanning tree $T$ is $\mathrm{wt}\, T = \sum\_{e \in T} a\_e + (n-1)\lambda$. It follows for any $\lambda \in \mathbb{R}$ the minimum spanning tree is just the minimum spanning tree gotten by weighting all edges with the weights $a\_e$.


