시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 0 0 0 0.000%

문제

้เฒ่าเต่าได้ค้นพบอาณาจักรโบราณแห่งหนึ่ง ประกอบไปด้วยเกาะต่างๆ จํานวน 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" โดยไม่มีเครื่องหมายคําพูด

예제 입력

2
3
1 2
2 3
5 20 -10
1 0 1
4
1 2
2 3
3 4
-1 5 -20 -1
1 0 0 1

예제 출력

15
Stay Home

힌트