## tree
struct Tree{newicktype, Teltype, Pareltype, idseltype, nameseltype}
    newick::newicktype   #   (:id, :data, :parent, :children)
    T::Vector{Teltype}
    Par::Vector{Pareltype}
    ids::Vector{idseltype}
    names::Vector{nameseltype}
    lids::Vector{idseltype}
    lnames::Vector{nameseltype}
    lastone::Vector{Bool} # true if it is the last child when running forwards
    n::Int64
end

function Tree(S::String)
    nwtree = readnw(S)

    ids = map(x->x.id, prewalk(nwtree))
    names = map(x->x.data.name, prewalk(nwtree))
    n = length(ids)
    # leaves
    l = getleaves(nwtree)
    lids = map(x -> Int(x.id), l)
    lnames = map(x->x.data.name, l)
    #@assert issubset(tipslist[:,1], lnames)

    # extract parents and time spans (on segments)
    Par = zeros(Int, n)  # parent ids
    T = zeros(n)  # time spans
    for node in prewalk(nwtree)
        isroot(node) && continue
        p = node.parent.id
        Par[node.id] = p
        T[node.id] = T[p] + node.data.distance
    end
    @assert all(Par .< 1:n)

    lastone = zeros(Bool,n)
    parentdone = zeros(Bool,n)
    for i ∈ n:-1:2
        if !parentdone[Par[i]]
            lastone[i] = true
            parentdone[Par[i]] = true
        end
    end
    Tree{typeof(nwtree), eltype(T), eltype(Par), eltype(ids), eltype(names)}(nwtree,  T, Par, ids, names, lids, lnames,lastone, n)
end





## read tree (very simple example)
S = "(A:0.6,B:0.2,(C:0.3,D:0.4)E:0.5)F;"
S20 = "(((t20:0.1377639426,t8:0.3216105914):0.461882598,(((t14:0.09650261351,t12:0.5344695284):0.1058950284,(t1:0.7008816295,t13:0.8587384557):0.7271672823):0.8026451592,(t6:0.5240857233,(t16:0.451590274,t10:0.4654036982):0.8569358122):0.140687139):0.7207935331):0.06727131596,((((t17:0.03115223325,t18:0.8930883685):0.6862687438,t9:0.4896655723):0.3056753092,t3:0.2549535078):0.07862622454,(((t4:0.03973490326,t5:0.4096179632):0.3020580804,t15:0.06550096255):0.2660011558,(t7:0.3895205685,((t19:0.165174433,t2:0.6469203965):0.2730371242,t11:0.2700119715):0.8393620371):0.02117527928):0.206376995):0.6012785432);"
S50 = "((((((t23:0.5766009684,t33:0.9917489749):0.3572315329,(t40:0.4535627225,t25:0.1296473157):0.9540394924):0.4740875189,(t6:0.946340692,t47:0.386682119):0.1535291784):0.07034701738,((((t49:0.6612032412,t27:0.1606025242):0.1527153626,t15:0.1854858669):0.5782065149,t50:0.3087045723):0.0759275395,((t17:0.258283512,t35:0.7651973176):0.2003453802,t2:0.4033703087):0.2418845498):0.6834833182):0.4268306631,(((t26:0.1744227773,(t16:0.6275201498,t10:0.09013780276):0.1857208994):0.8804157388,(t28:0.626011228,t46:0.8026940082):0.7066663445):0.6334459039,(t45:0.3075582262,t42:0.2759609232):0.05279792193):0.4003514573):0.5333229457,((((t30:0.05955170072,t41:0.2500256761):0.04172409023,((t19:0.3332289669,t31:0.6650944015):0.2450174955,t9:0.3372890623):0.2041792406):0.3337947708,t1:0.9396123393):0.0896910606,(((((t12:0.1379979164,t43:0.9007850592):0.703310129,(t11:0.3347885907,(t22:0.7190679635,t14:0.8988074451):0.1574828231):0.9644375315):0.137505424,((t37:0.7556577872,t8:0.3481238757):0.7712922962,(t7:0.7946650374,t48:0.8638419164):0.338934626):0.7507952554):0.5193078597,(t4:0.2408366969,(((t29:0.7862726359,t38:0.4319011718):0.8655222375,((t20:0.09156441619,t3:0.5975058537):0.3240908289,(t34:0.7324223334,t32:0.1348467385):0.4636785307):0.7708284601):0.7991992962,t39:0.2996040138):0.4087550903):0.1688272723):0.7225795928,(((t44:0.02794037666,t5:0.09033886855):0.5778779227,(t24:0.8744501146,((t21:0.2940180032,t18:0.03399693617):0.8231791619,t13:0.5192477896):0.5669933448):0.9547001948):0.8561708115,t36:0.9225172002):0.02867545444):0.1595393196):0.1254606678);"

# S20coal = "(((((t5:0.01408886814,t6:0.01408886814):0.03926824924,t3:0.05335711738):0.3769529348,t17:0.4303100522):0.6904821712,((t2:0.05400246327,(t19:0.04515631227,t7:0.04515631227):0.008846151006):0.02843109882,t15:0.08243356209):1.038358661):0.6759374458,(t12:0.5094458799,((t11:0.09067183363,(t4:0.08830667144,t1:0.08830667144):0.002365162193):0.2392304005,((t13:0.1499179245,((t10:0.01410801788,t20:0.01410801788):0.01360477778,t8:0.02771279566):0.1222051288):0.1061152139,(t16:0.1612987658,((t18:0.03933683292,t9:0.03933683292):0.008828557137,t14:0.04816539006):0.1131333758):0.09473437257):0.07386909574):0.1795436458):1.287283789);"

S20coal =  "(((t19:1.201139146,(t16:0.2402278292,t11:0.2402278292):0.9609113167):2.642506121,(t12:3.603417438,((t14:1.921822633,t17:1.921822633):0.9609113167,(t2:2.642506121,t7:2.642506121):0.2402278292):0.7206834875):0.2402278292):0.7206834875,((t20:3.122961779,((t6:0.4804556584,t4:0.4804556584):1.201139146,((t10:0.7206834875,t3:0.7206834875):0.2402278292,t9:0.9609113167):0.7206834875):1.441366975):1.201139146,(((t18:2.162050463,(t5:1.441366975,t8:1.441366975):0.7206834875):1.201139146,t13:3.363189608):0.7206834875,(t15:2.402278292,t1:2.402278292):1.681594804):0.2402278292):0.2402278292);"
