| 题目名称 | 1672. [SPOJ 375] 难存的情缘 |
|---|---|
| 输入输出 | qtree.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-07-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：293， 提交：735， 通过率：39.86% | ||||
 TAT |
100 | 0.067 s | 3.68 MiB | C |
|
TAT |
100 | 0.135 s | 0.79 MiB | C++ |
 HeHe |
100 | 0.139 s | 0.91 MiB | C++ |
 AAAAAAAAAA |
100 | 0.141 s | 1.14 MiB | C++ |
|
HeHe |
100 | 0.142 s | 0.91 MiB | C++ |
 kZime |
100 | 0.146 s | 0.97 MiB | C++ |
|
TAT |
100 | 0.146 s | 4.14 MiB | C++ |
 ztx |
100 | 0.159 s | 0.87 MiB | C++ |
|
ztx |
100 | 0.160 s | 1.12 MiB | C++ |
 真呆菌 |
100 | 0.162 s | 1.18 MiB | C++ |
| 关于 难存的情缘 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
重题了
 ┭┮﹏┭┮
2023-12-07 20:42
19楼
| ||||
|
A1个点 WA9个点怎么办啊 求大佬指点
 李俊辉
2019-08-11 16:05
18楼
| ||||
|
开心1A
 TARDIS
2017-09-05 07:13
17楼
| ||||
|
用fread的时候千万不要用scanf......
fread把文件读完了scanf还读个鬼....... 还有如果把边权转化为点权时用线段树求区间最大值时一定不要把LCA给加上去。。。。 | ||||
|
scanf比cin快太多
  ~玖湫~
2017-06-11 11:06
15楼
| ||||
|
读入有毒
 | ||||
|
第一道树剖留念
 Hzoi_Mafia
2017-06-11 09:08
13楼
| ||||
|
%%%kito
| ||||
|
第一次用guide写树剖，感觉爽飞了！
| ||||
|
我说自己怎么错了...
今天一看发现自己忘了忽略LCA= = | ||||
BaDBoY
FoolMike
AntiLeaf【题目描述】
一天机房的夜晚，无数人在MC里奋斗着。。。
大家都知道矿产对于MC来说是多么的重要，但由于矿越挖越少，勇士们不得不跑到更远的地方挖矿，但这样路途上就会花费相当大的时间，导致挖矿效率低下。
cjj提议修一条铁路，大家一致同意。
大家都被CH分配了一些任务：
zjmfrank2012负责绘制出一个矿道地图，这个地图包括家（当然这也是一个矿，毕竟不把家掏空我们是不会走的），和无数个矿，所以大家应该可以想出这是一个无向无环图，也就是一棵树。
Digital_T和cstdio负责铺铁路。。所以这里没他们什么事，两位可以劳作去了。
这个时候song526210932和RMB突然发现有的矿道会刷怪，并且怪的数量会发生变化。作为采矿主力，他们想知道从一个矿到另一个矿的路上哪一段会最困难。。。（困难值用zjm的死亡次数表示）。
【输入格式】
输入文件的第一行有一个整数N，代表矿的数量。矿的编号是1到N。
接下来N-1行每行有三个整数a,b,c，代表第i号矿和第j号矿之间有一条路，在初始时这条路的困难值为c。
接下来有若干行，每行是“CHANGE i ti”或者“QUERY a b”，前者代表把第i条路（路按所给顺序从1到M编号）的困难值修改为ti，后者代表查询a到b所经过的道路中的最大困难值。
输入数据以一行“DONE”结束。
【输出格式】
对每个“QUERY”操作，输出一行一个正整数，即最大困难值。
【样例输入】
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
【样例输出】
1
3
【提示】
对于60%的数据，1<=N<=50
对于100%的数据，1<=N<=10000，1<=c<=1000000,1<=操作次数<=100000
【来源】
由GDFRWMY 改编自SPOJ 375 QTREE
数据by cstdio