For　a　given　undirected　graph　with　each　edge　associated　with　a　weight　and　a　length,　the　constrained　minimum　spanning　tree　(CMST)　problem　aims　to　compute　a　minimum　weight　spanning　tree　with　total　length　bounded　by　a　given　fixed　integer　L∈　Z+.　In　the　paper,　we　first　present　an　exact　algorithm　with　a　runtime　O(mn2)　for　CMST　when　the　edge　length　is　restricted　to　0　and　1　based　on　combining　the　local　search　method　and　our　developed　bicameral　edge　replacement　approach.　Then　we　extend　the　algorithm　to　solve　a　more　general　case　when　the　edge　length　is　restricted　to　0,　1　and　2　via　iteratively　improving　a　feasible　solution　of　CMST　towards　an　optimum　solution.　At　last,　numerical　experiments　are　carried　out　to　validate　the　practical　performance　of　the　proposed　algorithms　by　comparing　with　previous　algorithms　as　baselines.　©　2020,　Springer　Science+Business　Media,　LLC,　part　of　Springer　Nature.