徐老师的采药plus
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师某天一觉醒来，发现自己穿越到了辰辰采药的那天！
他陪着辰辰跟医师来到了一个到处都是草药的山里，山里一共有 $n$ 个草药洞，第 $i$ 个草药洞中只有一株价值为 $w_i$ 的草药，而辰辰采集这株草药需要花费时间为 $v_i$，现在医师要求辰辰在规定的时间内尽可能的采到价值最大的草药，才能让辰辰拜他为师。
作为穿越而来的徐老师，自然决定要帮助辰辰完成这个任务！
众所周知，穿越的时候总是会带着一些金手指，例如各种系统或者老爷爷，然而徐老师的金手指是两个技能——闪现和时间重置！
徐老师发现自己的闪现技能有一定的限制，并不能随意闪烁到任意一个草药洞，也不能无限次数的闪烁
首先，对于徐老师处于第 $i$ 个草药洞时，他只能闪现到他看得见的草药洞，这里我们可以用 $u_i,v_i$ 来表示第 $u_i$ 个草药洞可以看得见第 $v_i$ 个草药洞，根据光路可逆原理， $v_i$ 自然也能看得见 $u_i$，每次闪现消耗 $1$ 单位的时间，并且徐老师采药不花费时间
现在徐老师会选择一个洞穴作为起点，但是被医师发现了徐老师在帮助辰辰
于是医师要求辰辰不许进入山洞，只允许徐老师进入，并且给出的时间要求会发生变化！
而徐老师的第二个技能——时间重置，允许徐老师返回到出发前，并且徐老师一共会使用 $m$ 次
第 $i$ 次出发时徐老师会选择 $x_i$ 作为起点山洞，并且医师给出的时间限制为 $y_i$
请注意，徐老师必须要在规定时间内返回起点才算完成任务，否则草药价值全当 $0$ 算
输入格式
第一行包含一个整数 $n$ 表示有 $n$ 个草药洞
第二行包含 $n$ 个整数 $w_i$ 分别表示每一株草药的价值
接下来 $n$ 行，每行两个整数 $u_i,v_i$ 表示两个洞穴能够互相看见
接下来一行包含一个整数 $m$ 表示徐老师重置了 $m$ 次时间
接下来 $m$ 行每行两个整数 $x_i,y_i$ 表示第 $i$ 个次重置的起点洞穴编号是 $x_i$，此时医师设置的时间限制为 $y_i$
对于 $20\%$ 的测试数据，满足$1\leq n\leq 6,1\leq m\leq 10$
对于 $40\%$ 的测试数据，满足$1\leq n\leq 8,1\leq m\leq 100$
对于另 $20\%$ 的测试数据，满足$1\leq n\leq 30,1 \leq m \leq 10^5$, 起点 $x_i$ 总是 $1$
对于 $80\%$ 的测试数据，满足$1\leq n\leq 30,1\leq m\leq 10^5$
对于 $100\%$ 的测试数据，满足$1\leq n\leq 100,1\leq m\leq 10^5, 1 \leq y_i,w_i \leq 10^5$
特别的保证：输入数据保证无重边、自环，并且保证每个草药洞都可达。
输出格式
输出共 $m$ 行，依次表示每个起点出发徐老师最多能采到的草药价值
样例
3
1 2 3
1 2
2 3
1 3
4
1 0
1 1
1 2
1 31
1
4
6提示
以 $1$ 为起点，时间为 $0$ 时，只能采到 $1$ 号草药，价值为 $1$以 $1$ 为起点，时间为 $1$ 时，时间不够徐老师出去再回来，所以只能采到 $1$ 号草药，价值为 $1$
以 $1$ 为起点，时间为 $2$ 时，徐老师可以从 $1$ 号闪现到 $3$ 号，再回到 $1$ 号，草药价值为 $1+3=4$
以 $1$ 为起点，时间为 $3$ 时，徐老师可以按照 $1->2->3->1$ 的顺序闪现，草药价值为 $1+2+3=6$
2023暑CSP-S复赛集训模拟赛五
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-8-1 22:15
- 结束于
- 2023-8-11 22:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 16
