P2972 [USACO10HOL]岩石和树木Rocks and Trees

    • 15通过
    • 27提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2010 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    My country's bigger than most

    And if asked I boast

    'Cause I'm really proud

    So I shout it loud

    Though our numbers are few

    We will welcome you

    Although we don't have history

    Gold medal winning teams

    Heroes or prisoners

    World famous volcanoes

    Still what we've got's glorious

    'Cause we've got

    Rocks and trees

    And trees and rocks

    And rocks and trees

    And trees and rocks

    And rocks and trees

    And trees and rocks

    And rocks and trees

    And trees and rocks

    And water

    -The Arrogant Worms, on Canada

    http://www.youtube.com/watch?v=P2Ca-vTapfU 
    After moving across the 49th parallel to Canada, the land of rocks and trees, Farmer John's cows invented a game to spend their leisure time on the pasture; naturally, it involved the rocks and trees! Cowboy Ted likes this game very much, but so poor is his luck that he always loses to other cows. This time, he is going to seek your help. 
    The game's rules are simple. It is played with a tree that has both N (2 <= N <= 10,000) nodes conveniently numbered 1..N and also N-1 branches. Node 1 is the root of this tree; except for node 1, node i has parent P_i (1 <= P_i < i). Initially, Each node contains some rocks (except the root node, which has no rocks). In particular, non-root node i has exactly R_i (1 <= R_i <= 1,000) rocks at the beginning of the game. 
    Two players alternate turns to play this game in turn, with Ted going first. In each turn, the current player can choose a non-root node i and move at most L (1 <= L <= 1,000) rocks from this node one branch closer to the root (i.e., move these rocks to the parent node). He must move at least one rock, and, of course, he cannot exceed the current number of rocks on this node. The game ends when a player can't make a legal move (i.e., when all the rocks are on node 1); that player loses. 
    Ted needs your help. He has given you the initial configuration of the game, and he will then make T (1 <= T <= 10,000) changes to the configuration one by one. Please help him determine, after each step, if he can win the game beginning from this configuration, assuming both he and his opponent use the best possible strategy. 
    Ted's changes are specified as two integers A_j (1 < A_j <= N) and B_j (1 <= B_j <= 1,000), meaning that Ted will change the number of rocks on node A_j to B_j (this is a 'set' not a 'subtract' or 'add'), and will then ask you whether he can win. Changes accumulate; node A_j's rocks stay at B_j until another change for A_j appears. 

    Consider this example with three nodes numbered as shown and the shape shown in Board 0. Initially, there are 5 rocks on node 2 and 3 rocks on node 3; see Board 1.

    For the first change, Ted removes 2 rocks from node 2 (thus leaving 3); see Board 2. For the second change, Ted removes 2 rocks from node 3 (thus leaving 1). Note that node 2 still has 3 rocks; see Board 3.

    1 - - -

    / \ / \ / \ / \

    2 3 5 3 3 3 3 1

    Board 0 Board 1 Board 2 Board 3

    Your program should determine in each case who wins.

    For about 30% of the test cases, N <= 10, and T <= 100, and no tree node will have more than 5 rocks on it after any of Ted's changes.

    Partial feedback will be provided for your first 50 submissions.

    农夫约翰在穿过北纬49度纬线进入祇有石头木头的土地,加拿大之后,他们的牛发明了一种新游戏来在草地上消磨闲暇时间;因为这个游戏把石头和木头(树)天衣无缝地结合在一起!小牛Ted灰常喜欢这个游戏,可是他的运气是多么糟糕他总是在这个游戏输给其它的牛。这次,他过来找你帮忙。

    这个游戏的规则很简单。这个游戏在一个有着1到N (2 <= N <= 10,000)一共N个节点,N-1条边的树上面进行。节点1是树根。除了节点1,节点i有一个父节点P_i (1 <= P_i < i)。一开始,每个节点都有一些石头(除了根节点,根节点没有石头)。

    具体来说,在游戏刚开始的时候非根节点i恰好有R_i (1 <= R_i <= 1,000)个石头。 游戏在两个玩家之间轮流进行,Ted先手。在每一轮,这轮的玩家可以选择一个非根节点,并且把最多L (1 <= L <= 1,000)个石头从这个节点向树根靠近一个单位(也就是说,把这些石头移动到它的父节点处)。并且这个玩家至少需要移动一个石子。当某个玩家没有办法移动石子的时候(也就是所有的石子都移动到节点1),游戏结束,这个玩家失败。

    Ted需要你的帮助。他得到了一开始一开始游戏的佈局,而且他将会对这个佈局一一进行T (1<= T <= 10,000)次修改。请帮助他确定,在每步修改之后,以这个佈局开局,在双方都用最优策略的前提下他是否能赢得这个游戏。 Ted的每次修改由两个数字A_j (1 < A_j <= N)和B_j (1 <= B_j <= 1,000)描述,表示Ted将会把节点A_j的石头数修改为B_j(注意这是一个“设定”操作,既不是“减少”也不是“增加”)。并且询问修改后谁会获胜。注意这些修改会累积,也就是节点A_j的石头数会一直保持在B_j个,知道新的A_j出现。

    你的程序应该确定在以每个状况作为开局时谁将获胜。 大约30%的测试数据有N <= 10且T <= 100。并且在Ted每次修改过后树上没有节点会超过5个石头。 你将会在你前50次提交的时候得到部份测试数据反馈。

    输入输出格式

    输入格式:

    * Line 1: Three space-separated integers: N, T, and L

    * Lines 2..N: Line i contains two space-separted integers: P_i and R_i

    * Lines N+1..N+T: Line j+N describes Ted's next change using two space-separated integers: A_j and B_j

    输出格式:

    * Lines 1..T: Line i contains 'Yes' if Ted can win the game after change i; and 'No' otherwise.

    输入输出样例

    输入样例#1: 复制
    3 2 10 
    1 5 
    1 3 
    2 3 
    3 1 
    
    输出样例#1: 复制
    No 
    Yes 
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。