HBC230424[CQOI2013]新NIM游戏,线性基,线性代数Tree题解

痛心疾首算法基础篇 2023-11-13 16:17:01 52 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

1以外，每个节点。i上都结有价值为。现在假设小明有个初始体力值。，否则无法通过该条链，注意这里的链是双向的，即如果可以从。t，从而再有可能移动到下个节点，已知小明一开始站在节点。1的位置，他需要获取价值总和至少为。题目保证所有节点宝石价值之和不小于。s，且每个节点上的宝石最多被摘取一次。

有一棵包含 n n个节点的``宝石树''。除了节点 1 1以外，每个节点 i(iin[2,n]) i(i∈[2,n])上都结有价值为 a_i a i 的宝石，且节点 u u与节点 v v之间的链长为 d_{uv} d uv 。现在假设小明有个初始体力值 t t。如果他想从节点 u u 经过链 d_{uv} d uv 走到节点 v v，从而获取节点 v v 上的宝石，那么需要保证 tgeq d_{uv} t≥d uv ，否则无法通过该条链。注意这里的链是双向的，即如果可以从 u u走到 v v，那也可以从 v v走到 u u。当到达节点 v v 时，小明立马会恢复初始体力值 t t，从而再有可能移动到下个节点。已知小明一开始站在节点 1 1的位置，他需要获取价值总和至少为 s s 的宝石，问他的初始体力值 t t最小是多少。题目保证所有节点宝石价值之和不小于 s s，且每个节点上的宝石最多被摘取一次。