<prompt> Kuna mti ambao haujaelekezwa wenye nodi za n zilizoandikwa kutoka 0 hadi n - 1, zilizo na kifundo 0. Umepewa safu kamili ya 2D kingo za urefu n - 1 ambapo kingoi ai, bi huonyesha kuwa kuna ukingo kati ya nodi ai na bi kwenye mti.Katika kila nodi i, kuna lango. Pia unapewa safu ya hata nambari kamili kiasi, ambapo kiasii inawakilisha: bei inayohitajika ili kufungua lango kwenye nodi i, ikiwa kiasii ni hasi, au, malipo ya pesa yaliyopatikana kwa kufungua lango kwenye nodi i, vinginevyo.Mchezo unaendelea kama ifuatavyo: Hapo awali, Alice yuko kwenye nodi 0 na Bob yuko kwenye nodi bob. Kwa kila sekunde, Alice na Bob kila husogea hadi kwenye kifundo kilicho karibu. Alice anasogea kuelekea nodi ya majani, huku Bob anasogea kuelekea nodi 0. Kwa kila nodi kwenye njia yao, Alice na Bob wanatumia pesa kufungua lango kwenye nodi hiyo, au wakubali thawabu. Kumbuka kwamba: Ikiwa lango ni tayari limefunguliwa , hakuna bei itahitajika, wala hakutakuwa na malipo yoyote ya fedha. Ikiwa Alice na Bob wanafikia nodi wakati huo huo , wanashiriki beizawabu kwa kufungua lango hapo. Kwa maneno mengine, ikiwa bei ya kufungua lango ni c, basi Alice na Bob hulipa c 2 kila mmoja. Vile vile kama malipo langoni ni c, wote wawili watapata c 2 kila mmoja. Ikiwa Alice anafikia nodi ya majani, anaacha kusonga. Vile vile, Bob akifikia nodi 0, anaacha kusogea. Kumbuka kwamba matukio haya ni huru ya kila moja.Rejesha _mapato ya juu zaidi halisi ambayo Alice anaweza kuwa nayo ikiwa atasafiri kuelekea eneo linalofaa zaidi la majani._Mfano wa 1:Ingizo: kingo 0,1,1,2,1,3,3,4, bob 3, kiasi -2,4,2,-4,6Pato: 6Maelezo:Mchoro hapo juu unawakilisha mti uliopewa. Mchezo unaendelea kama ifuatavyo:- Alice hapo awali yuko kwenye nodi 0, Bob kwenye nodi 3. Wanafungua milango ya nodi zao husika. Mapato halisi ya Alice sasa ni -2.- Alice na Bob wanahamia nodi 1. Kwa kuwa wanafika hapa kwa wakati mmoja, wanafungua lango pamoja na kushiriki thawabu. Mapato halisi ya Alice yanakuwa -2 42 0.- Alice anasonga kwenye nodi 3. Kwa kuwa Bob tayari alifungua lango lake, mapato ya Alice bado hayajabadilika. Bob anasonga kwenye nodi 0, na anaacha kusonga.- Alice anasonga kwenye nodi 4 na kufungua lango hapo. Mapato yake halisi yanakuwa 0 6 6.Sasa, si Alice wala Bob anayeweza kufanya hatua nyingine, na mchezo unaisha.Haiwezekani kwa Alice kupata mapato ya juu.Mfano wa 2:Ingizo: kingo 0,1, bob 1, kiasi -7280,2350Pato: -7280Maelezo:Alice anafuata njia 0-1 ilhali Bob anafuata njia 1-0.Kwa hivyo, Alice anafungua lango kwa nodi 0 tu. Kwa hivyo, mapato yake halisi ni -7280.Vikwazo: 2 n 105 edges.length n - 1 kingoi.urefu 2 0 ai, bi n ai ! bi kingo inawakilisha mti halali. 1 bob n kiasi.urefu n kiasii ni nambari kamili sawa katika safu -104, 104.  <response>: kutoka kwa makusanyo leta defaultdictdef dfsnodi, mzazi, bob, wakati, alice_mapato, res, kiasi, mti: ikiwa muda bob au kiasinode 0: alice_mapato kiasinodi kwingine: alice_mapato kiasinodi 2 kiasi nodi 0 ni_jani Kweli kwa mtoto kwenye mtinodi: kama mtoto ! mzazi: ni_jani Si kweli dfsmtoto, nodi, bob, muda 1, mapato_alice, res, kiasi, mti ikiwa ni_jani: res0 maxres0, alice_mapatodef maxNetIncomekingo, bob, kiasi: mti defaultdictorodha kwa makali katika kingo: mtimakali0.ongezamakali1 mtimakali1.ongezamakali0 res -100000 dfs0, -1, bob, 0, 0, res, kiasi, mti rejesha majibu0 