| 题目名称 | 1978. [TJOI 2015] 旅游 |
|---|---|
| 输入输出 | tjoi2015_travel.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 9 |
| 题目来源 |
 cstdio
于2015-05-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：36， 提交：97， 通过率：37.11% | ||||
 ┭┮﹏┭┮ |
100 | 0.777 s | 12.05 MiB | C++ |
 Owaski |
100 | 0.806 s | 18.05 MiB | C++ |
 Pine |
100 | 0.813 s | 5.14 MiB | C++ |
 HT008 |
100 | 0.873 s | 6.62 MiB | C++ |
 Youngsc |
100 | 0.880 s | 5.59 MiB | C++ |
 ztx |
100 | 0.894 s | 3.20 MiB | C++ |
 wumingshi |
100 | 0.901 s | 6.58 MiB | C++ |
 pretend_fal |
100 | 0.908 s | 18.93 MiB | C++ |
 Asm.Def |
100 | 0.923 s | 7.22 MiB | C++ |
 thomount |
100 | 0.946 s | 10.02 MiB | C++ |
| 本题关联比赛 | |||
| 郑州市创意编程大赛复现赛 | |||
| 关于 旅游 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
超级无敌豪华难难难nanananananana
| ||||
|
md居然是dfs写挂了。。。
wumingshi
2017-08-16 14:53
10楼
| ||||
|
居然每次只能交易一次。。害得我写了个巨难写难调的恶心数据结构后不得不重写！！
 _Itachi
2017-04-13 11:08
9楼
| ||||
|
QAQ...bzoj上是可以过得....是我的LCT姿势不对么....
| ||||
|
看来是LCT写挂了，为什么没有树链剖分跑的快啊= =
| ||||
|
树链剖分就是干！！
| ||||
|
建两颗线段树，常数大如狗。
| ||||
|
回复 @cstdio :
LCT欢迎您 | ||||
|
线段树都能写挂，还玩不玩了= =
| ||||
dydxh
天一阁
RP++1978. [TJOI 2015] 旅游
★★★☆ 输入文件：tjoi2015_travel.in
输出文件：tjoi2015_travel.out
简单对比时间限制：1 s 内存限制：128 MiB
【题目描述】
为了提高智商，ZJY准备去往一个新世界去旅游。这个世界的城市布局像一棵树。每两座城市之间只有一条路径可以互达。每座城市都有一种宝石，有一定的价格。ZJY为了赚取最高利益，她会选择从A城市买入再转手卖到B城市。由于ZJY买宝石时经常卖萌，因而凡是ZJY路过的城市，这座城市的宝石价格会上涨。让我们来算算ZJY旅游完之后能够赚取的最大利润。（如a城市宝石价格为v，则ZJY出售价格也为v）
【输入格式】
第一行输入一个正整数N表示城市个数。
接下来一行输入N个正整数表示每座城市宝石的最初价格p，每个宝石的初始价格不超过100.
第三行开始连续输入N-1行，每行有两个数字x和y。表示x城市和y城市有一条路径。城市编号从1开始。下一行输入一个正整数Q表示询问次数。
接下来Q行每行输入三个正整数a,b,v，表示ZJY从a旅游到b，城市宝石价格上涨v。
【输出格式】
对于每次询问，输出ZJY可能获得的最大利润，如果亏本了则输出0。
【样例输入】
3
1 2 3
1 2
2 3
2
1 2 100
1 3 100
【样例输出】
1
1
【提示】
对于30%的数据，有0 < N ≤ 100, 0 < Q ≤ 10000。
对于100%的数据，有0 < N ≤ 50000, 0 < Q ≤ 50000。