<prompt> Imetolewa kwa mti ambao haujaelekezwa unaojumuisha wima n yenye nambari kutoka 1 hadi n. Chura anaanza kuruka kutoka vertex 1. Katika sekunde moja, chura huruka kutoka kwenye kipeo chake cha sasa hadi kipeo kingine kisichotembelewa ikiwa zimeunganishwa moja kwa moja. Chura hawezi kuruka nyuma kwenye vertex iliyotembelewa. Iwapo chura anaweza kuruka hadi vipeo kadhaa, anaruka bila mpangilio kwenda kwa mmoja wao na uwezekano sawa. Vinginevyo, wakati chura hawezi kuruka kwenye vertex yoyote isiyotembelewa, inaruka milele kwenye vertex sawa.Kingo za mti ambao haujaelekezwa zimetolewa katika safu kingo, ambapo kingoi ai, bi inamaanisha kuwa kuna ukingo unaounganisha vipeo ai na bi._Rejesha uwezekano kwamba baada ya sekunde t chura yuko kwenye kipeo lengwa._ Majibu ndani ya 10-5 ya jibu halisi yatakubaliwa.Mfano wa 1:Ingizo: n 7, kingo 1,2,1,3,1,7,2,4,2, 6,3,5, t 2, lengo 4Pato: 0.16666666666666666Maelezo: Kielelezo hapo juu kinaonyesha grafu iliyotolewa. Chura huanza kwenye kipeo cha 1, akiruka na uwezekano 13 kwa kipeo 2 baada ya pili 1 na kisha kuruka na uwezekano wa 12 kwa kipeo cha 4 baada ya pili 2. Hivyo uwezekano wa chura uko kwenye kipeo 4 baada ya sekunde 2 ni 13 12 16 0.16666666666666666.Mfano wa 2:Ingizo: n 7, kingo 1,2,1,3,1,7,2,4,2, 6,3,5, t 1, lengo 7Pato: 0.3333333333333333Maelezo: Kielelezo hapo juu kinaonyesha grafu iliyotolewa. Chura huanza kwenye kipeo cha 1, akiruka na 13 0.33333333333333333 uwezekano wa vertex 7 baada ya pili 1.Vikwazo: 1 n 100 edges.length n - 1 kingoi.urefu 2 1 ai, bi n 1 t 50 1 lengo n  <response>: kutoka kwa makusanyo leta defaultdictdef dfsnodi, mzazi, t, lengo, grafu, prob, ans: ikiwa t 0: ikiwa nodi lengo: ans0 prob kurudi has_child Uongo kwa jirani kwenye graphnodi: ikiwa jirani ! mzazi: has_child Kweli dfsjirani, nodi, t - 1, lengo, grafu, prob lengraphnodi - 1 ikiwa nodi ! 1 mwingine 0, ans ikiwa sio has_child na nodi target: ans0 probdef frogPositionn, edges, t, target: grafu defaultdictorodha kwa a, b katika kingo: grafua.ongezab grafub.ongezaa chini 0.0 dfs1, -1, t, lengo, grafu, 1.0, ans rudisha jibu0 