10297번 - ผู้เฒ่าเต่า 다국어

문제

้เฒ่าเต่าได้ค้นพบอาณาจักรโบราณแห่งหนึ่ง ประกอบไปด้วยเกาะต่างๆ จํานวน N เกาะ ซึ่งจะแทนด้วยจํานวนเต็ม 1,2,3,...,N แต่ละเกาะเชื่อมกันด้วยสะพานผุๆ ซึ่งสามารถข้ามได้เพียงครั้งเดียวก็จะพังลง และเกาะต่างๆในอาณาจักรเชื่อมต่อกันเป็นต้นไม้ (นั่นคือไม่มีการเชื่อมเป็นวงรอบ) ในแต่ละเกาะมีเวทย์มนต์ที่จะมีผลต่ออายุขัยของผู้ที่เท้าสัมผัสเกาะ กล่าวคือ เมื่อผู้เฒ่าเต่าเท้าสัมผัสเกาะที่ i อายุขัยของเขาจะมีค่าเป็น (อายุขัยก่อนเท้าสัมผัสเกาะ) + Xi วัน โดยที่ Xi สามารถมีค่าเป็นลบได้

การเดินทางมายังอาณาจักรนี้ทําได้โดยกระโดดร่มลงจากเครื่องบิน และการเดินทางออกจากเกาะคือ จุดพลุสัญญาณให้เครื่องบินมารับ แต่บางเกาะของอาณาจักรนี้มีสัตว์ร้ายอยู่ ซึ่งหากกระโดดร่มลงมาที่เกาะนี้หรือจุดพลุสัญญาณ จะทําให้สัตว์ร้ายอาละวาด จึงต้องกระโดดร่มหรือจุดพลุสัญญาณบนเกาะที่ไม่มีสัตว์ร้ายเท่านั้น ให้หาว่าถ้าผู้เฒ่าเต่ามีพลุสัญญาณอันเดียว(นั่นคือ เข้าและออกจากอาณาจักรได้แค่ครั้งเดียว) จะสามารถยืดอายุขัยตัวเองไปได้มากที่สุดกี่วัน

รับประกันว่าผู้เฒ่าเต่ามีอายุขัยเหลือมากพอที่จะเดินทางในอาณาจักรนี้ได้ นั้นคือไม่ต้องกังวลถึงกรณีที่ เมื่อเข้าสู่เกาะที่ทําให้อายุขัยลดลง แล้วผู้เฒ่าเต่าจะหมดอายุขัยและไม่สามารถเดินทางต่อได้

입력

บรรทัดแรกระบุจํานวนเต็ม T <= 10 บ่งบอกจํานวนชุดข้อมูลทดสอบ

• แต่ละชุดข้อมูลทดสอบประกอบด้วย จํานวนเต็ม N <= 100,000 และข้อมูลอีก N+1 บรรทัด
• N-1 บรรทัดแรก ประกอบด้วยจํานวนเต็มสองจํานวน 1 <= a, b <= N โดย a < b คั่นด้วยช่องว่างหนึ่งช่อง ซึ่งหมายความว่ามีสะพานผุๆเชื่อมเกาะหมายเลข a และเกาะหมายเลข b
• อีกหนึ่งบรรทัดประกอบด้วยจํานวนเต็ม N จํานวน แต่ละจํานวนคั่นด้วยช่องว่างหนึ่งช่อง โดยจํานวนที่ i บอกค่าของ Xi ; -10,000 < Xi < 10,000
• และบรรทัดสุดท้ายประกอบด้วยจํานวนเต็ม N จํานวน แต่ละจํานวนคั่นด้วยช่องว่างหนึ่งช่อง จํานวนที่ iเป็น 1 ถ้าเกาะนั้นสามารถกระโดดร่มและ/หรือ จุดพลุสัญญานได้ (ไม่มีสัตว์ร้าย) และเป็น 0 ถ้าไม่สามารถทําได้ (มีสัตว์ร้าย)

출력

ประกอบด้วยจํานวนเต็มหนึ่งจํานวน เป็นจํานวนวันที่มากที่สุดที่สามารถยืดอายุขัยออกไปได้ แต่หากจํานวนนี้มีค่าไม่มากกว่าศูนย์ ผู้เฒ่าเต่าควรจะอยู่บ้าน และให้พิมพ์คําตอบว่า "Stay Home" โดยไม่มีเครื่องหมายคําพูด

제한

힌트