Skip to content

11126: 【原1126】小k的旅行计划

题目

题目描述

author: Kuan Yang 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1126

Description

小k今年的暑假时间非常短,但他还是想出去旅游,小k所在的国家一共有N个城市,有N – 1条双向的道路把这N个城市都连接在一起。小k是一个不喜欢重复经过城市的同学,因此对他来说任意两个城市之间只存在一条路径。现在小k给每个城市标了两个数(x,y),意思是如果他在这个城市旅游需要停留x天,可以得到y点愉悦度。因为小k的暑假时间很短,一共只能旅游k天,他希望合理地选择一些城市停留,使得他的愉悦度最大。这个国家的城际交通系统非常发达,所以你可以认为小k在路上的时间是忽略不计的。

Input Format

第1行输入2个正整数:N和k,分别表示城市的数目和小k可以去旅游的天数

第2~N行描述了这个国家的道路系统

每行输入2个正整数:x和y,表示城市x和城市y之间有一条双向道路

第N+1行输入N个非负整数:a_1, a_2, a_3,……,a_N,表示小k在每个城市旅游需要停留的时间

第N+2行输入N个非负整数:b_1, b_2, b_3,……,b_N,表示小k在每个城市旅游可以获得的愉悦度

第N+3行输入1个正整数:Q,表示小k的旅游计划中的询问数目

第N+4~N+3+Q行,每行两个正整数:p和q,描述了小k的一条旅游计划

小k将从城市p出发,沿着从p到q的路,到沿途经过的一些城市旅游,并最终到达城市q。小k可以不在城市p和q停留,但是他希望能合理选择途中停留的城市使得在总停留天数不超过k天的情况下他获得的愉悦值最大。

对于50%的数据,N≤100 ,Q≤100; 对于100%的数据,N≤5,000 ,Q≤5,000 ,k≤40. 输入数据保证所有的城市都是连通的。

Output Format

输出文件一共Q行

对于小k的每一组询问,输出一行一个正整数表示这个旅游计划可以让小k获得的最大愉悦度

Sample Input

5 5
1 2
2 3
2 4
4 5
1 1 1 1 1
1 1 1 1 1
3
1 4
2 5
3 4

Sample Output

3
3
3

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!