| 题目名称 | 1799. [国家集训队2012]tree(伍一鸣) |
|---|---|
| 输入输出 | nt2012_wym_tree.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 2500 ms (2.5 s) |
| 内存限制 | 64 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-11-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：128， 提交：305， 通过率：41.97% | ||||
 Hallmeow |
100 | 3.255 s | 7.61 MiB | C++ |
 lmm |
100 | 3.455 s | 3.77 MiB | C++ |
|
Hallmeow |
100 | 3.569 s | 7.21 MiB | C++ |
 AntiLeaf |
100 | 4.428 s | 3.72 MiB | C++ |
 gls1196 |
100 | 4.429 s | 3.75 MiB | C++ |
 sxysxy |
100 | 4.518 s | 4.60 MiB | C++ |
 xzz_666 |
100 | 4.591 s | 3.82 MiB | C++ |
|
xzz_666 |
100 | 4.638 s | 3.44 MiB | C++ |
|
lmm |
100 | 4.659 s | 3.55 MiB | C++ |
 呵呵酵母菌 |
100 | 4.699 s | 7.94 MiB | C++ |
| 关于 tree(伍一鸣) 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
人蠢常数大
| ||||
|
呀。榜首了。
| ||||
|
人傻大常数
 CSU_Turkey
2017-12-26 21:09
16楼
| ||||
|
| ||||
|
这个模数开unsigned就可以了，不用每次强转long long
 _Itachi
2017-04-07 07:17
14楼
| ||||
|
蒟蒻忘了乘子树大小，真是辣鸡一只……
| ||||
|
回复 @AntiLeaf :
$\sum_{i | n} \sum_{j | n} {[n | i j] \mu(\frac{i j}{n}) \left\lfloor\frac{a}{i}\right\rfloor \left\lfloor\frac{b}{j}\right\rfloor}$  YGOI_真神名曰驴蛋蛋
2016-12-31 13:51
12楼
| ||||
|
LCT get√
| ||||
|
太慢了……
发现不用递归栈就不会超时了 | ||||
|
回复 @Chenyao2333 :
成功仿制然后上榜233333，论常数的优越性 | ||||
可以的.
FoolMike
TenderRun
Fmuckss1799. [国家集训队2012]tree(伍一鸣)
★★★★ 输入文件：nt2012_wym_tree.in
输出文件：nt2012_wym_tree.out
简单对比时间限制：2.5 s 内存限制：64 MiB
【问题描述】
一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：
+ u v c：将u到v的路径上的点的权值都加上自然数c；
- u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；
* u v c：将u到v的路径上的点的权值都乘上自然数c；
/ u v：询问u到v的路径上的点的权值和，求出答案对于51061的余数。
【输入格式】
第一行两个整数n，q
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
【输出格式】
对于每个/对应的答案输出一行
【样例输入】
3 2 1 2 2 3 * 1 3 4 / 1 1
【样例输出】
4
【数据规模和约定】
10%的数据保证，1<=n，q<=2000
另外15%的数据保证，1<=n，q<=5*10^4，没有-操作，并且初始树为一条链
另外35%的数据保证，1<=n，q<=5*10^4，没有-操作
100%的数据保证，1<=n，q<=10^5，0<=c<=10^4
【来源】
国家集训队 2012 伍一鸣