The world can be regarded as an undirected connected graph of. m undirected roads between the cities. Now you, the life game player, are going to play the life game on the world graph.k social ability points. You can earn social ability points by living and working. Specifically, you can earn. social ability points by living and working in the. i-th city. But in this problem, you cannot earn social ability points duplicatedly in one city, so you want to travel the world and earn more social ability points. However, the roads are not easy. Specifically, there is an ability threshold. So as you can see, the life game is just living, working and traveling repeatedly. There are. q game saves. For each game save, the initial city and social ability point is given and the player has not lived or worked in any city. Now you, the real life game player, need to determine the maximum possible number of social ability points you can have in the end of the game and output it for each given game save.
Life is a game. The world can be regarded as an undirected connected graph of n n cities and m m undirected roads between the cities. Now you, the life game player, are going to play the life game on the world graph. Initially, you are at the x x-th city and of k k social ability points. You can earn social ability points by living and working. Specifically, you can earn a_i a i social ability points by living and working in the i i-th city. But in this problem, you cannot earn social ability points duplicatedly in one city, so you want to travel the world and earn more social ability points. However, the roads are not easy. Specifically, there is an ability threshold w_i w i for the i i-th road, you should be of at least w_i w i social ability points to go through the road. Moreover, Your social ability point will not decrease when passing roads but just need to be at least w_i w i if you want to go through the i i-th road. So as you can see, the life game is just living, working and traveling repeatedly. There are q q game saves. For each game save, the initial city and social ability point is given and the player has not lived or worked in any city. Now you, the real life game player, need to determine the maximum possible number of social ability points you can have in the end of the game and output it for each given game save.
标签： HBC231127Colorful Tree 最近公共祖先（LCA） 图论 数据结构 DFS序Life is a Game题解
