| 题目名称 | 2532. [HZOI 2016]树之美 |
|---|---|
| 输入输出 | skytree.in/out |
| 难度等级 | ★★ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Sky_miner
于2016-11-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：15， 提交：29， 通过率：51.72% | ||||
 冷曦 |
100 | 0.417 s | 30.80 MiB | C++ |
 ┭┮﹏┭┮ |
100 | 0.967 s | 51.80 MiB | C++ |
 再见 |
100 | 0.989 s | 32.71 MiB | C++ |
 846047746 |
100 | 1.067 s | 30.83 MiB | C++ |
|
846047746 |
100 | 1.111 s | 30.83 MiB | C++ |
|
Go灬Fire |
100 | 1.356 s | 33.88 MiB | C++ |
 aufeas |
100 | 1.704 s | 25.08 MiB | C++ |
 hjj |
100 | 1.955 s | 29.45 MiB | C++ |
|
hjj |
100 | 2.125 s | 32.72 MiB | C++ |
 FoolMike |
100 | 2.173 s | 100.43 MiB | C++ |
| 关于 树之美 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
ll
| ||||
|
md最后一组数据有毒。O(Tnk)的做法神tm超时。本机测试2s
Add: bfs做法Knt的常数约为3，dfs常数约为2...所以本地前者2s，后者1.5s... 没有使用memset是因为大数据它加速，小数据会减速 然后树的bfs虽然理论是O(n)，常数却是for(i,1,n)的好几倍  喵喵喵
2016-11-10 16:52
7楼
| ||||
|
回复 @多冷的隆冬哒哒~ :
学长，，本机测试1s的标程上去跑了三四秒  Sky_miner
2016-11-10 15:21
6楼
| ||||
|
回复 @Sky_miner :
明白了，感谢大神指教。生日快乐！！ 这样我们知道了一件事，stl的stack真的很慢！！ 对于这个题，我们可以考虑在树上按照深搜序暴力换根，复杂度O(nkT)，还是可以接受的 | ||||
|
回复 @Mike is Fool :
本来打算只开1s时限的，但是标程在COGS上最后一个点跑了三四秒，所以开了五秒时限 您的暴力换根在我本地AC，但是极限数据跑了0.998s，接近超时 但是COGS的老爷机嘛，，，只能优化常数了。。。 我卡了卡常，用您的代码AC了 Sky_miner
2016-11-09 17:03
4楼
| ||||
|
题解：http://www.cnblogs.com/Skyminer/p/6047542.html
Sky_miner
2016-11-09 16:38
3楼
| ||||
|
这个题不就是在树上暴力换根吗？？
| ||||
|
SM生快
 YGOI_真神名曰驴蛋蛋
2016-11-09 08:00
1楼
| ||||
【题目描述】
Sky_miner的生日到了！
为了庆祝Sky_miner的生日，Sky_miner找到一颗树
这颗树可是非常有趣呢。
Sky_miner把这棵树玩来玩去，突然发现这些树上有一些果子！但是这些果子是有灵气的，在摘下一个果子的同时，与这个果子距离不超过k的所有果子都会由于感受到灵气流动而爆炸消失。
但是Sky_miner就喜欢看到这种场面，所以Sky_miner要好好想想要怎么摘下这些果子。所以就需要你帮忙了。
定义一个对于节点u询问的结果是在树上所有与u距离不超过k的点数（包括其本身）。
定义树上点对<u,v>的距离表示从u到v的最短路径上经过的边的数量。
Sky_miner会询问1~n每个点，但是你才不想帮助Sky_miner，所以你决定告诉Sky_miner的所有询问的异或和,让Sky_miner自己在风中凌乱。
【输入格式】
多组测试数据
行有一个正整数T，表示测试数据的组数T <= 5
每一组测试数据共一行包括四个正整数n,k,A,B其中n,k如题目含义相符。
第i(2<=i<=n)个点的父亲是(A*i + B)%(i-1) + 1。
第一个点没有父亲
【输出格式】
对于每一组测试数据，输出共一行，为题目所求
【样例输入】
2
5 2 3 3
7 6 6 6
【样例输出】
3
7
【提示】
n <= 500000,k <= 10,A,B <= 1000000
【来源】
HZOI 2016