Flowers
Time limit1sMemory limit1024 MB
Given a rooted tree of N pots with water needs A_i, decide whether the first player wins the watering game when both players play optimally.
- Level
Hard8 of 10
- Topics
- Game theory, Tree, Dynamic programming
- Solved
- No attempts yet
Problem
Hoshi installed wall-mounted flower pots numbered to as follows. First, he hung pot at the highest position. Then, for each from to in order, he hung pot lower than pot , where , and connected a water pipe that flows downward from pot to pot .
After installing all the pots, Hoshi planted one flower in each pot. The flower in pot needs units of water per day, and he planted the flowers so that holds.
Hoshi got bored of watering the flowers the same amount every day. He decided to play the following game with his friend Yuki.
Hoshi starts, and Hoshi and Yuki take turns watering the pots under these rules.
- If pot has not yet received units of water, choose pot . Otherwise, choose any pot with that has not yet received units of water, where pot has already received units of water.
- Close all pipes connected to pot and water pot until its total water reaches . Or, add unit of water to pot and to every pot reachable from pot through the pipes, starting from pot .
If a player cannot water any pot on their turn, that player loses.
Assuming both players play optimally to win, determine who wins.
Input
The first line contains the number of test cases . ()
Each test case consists of three lines. The first line contains , the number of pots. ()
The second line contains , separated by spaces. ()
The third line contains , separated by spaces. ()
The sum of over all test cases does not exceed .
All input values are integers.
Output
For each test case, print First if Hoshi wins, or Second if Yuki wins, on a separate line.