【NOIP模拟赛】小奇的仓库

2015年3月30日1,5463

原题:【East!_XI】第一个问题 2015年10月4日hzwer改写了题面

【题目背景】

小奇采的矿实在太多了,它准备在喵星系建个矿石仓库。令它无语的是,喵星系的货运飞船引擎还停留在上元时代!

【问题描述】

喵星系有n个星球,星球以及星球间的航线形成一棵树。

从星球a到星球b要花费[dis(a,b) Xor M]秒。(dis(a,b)表示ab间的航线长度,Xor为位运算中的异或)

为了给仓库选址,小奇想知道,星球i(1<=i<=n)到其它所有星球花费的时间之和。

【输入格式】

第一行包含两个正整数n,M。
接下来n-1行,每行3个正整数a,b,c,表示a,b之间的航线长度为c。

【输出格式】

n行,每行一个整数,表示星球i到其它所有星球花费的时间之和。

【样例输入】

4 0

1 2 1

1 3 2

1 4 3

【样例输出】

6

8

10

12

【数据范围】

序号 N M

1 6 0

2 100 5

3 2000 9

4 50000 0

5 50000 0

6 50000 1

7 50000 6

8 100000 10

9 100000 13

10 100000 15

保证答案不超过2*10^9

题解

出题人18357:

算法1:

不会写函数的小伙伴们,我们只需要写个floyd,就有10分啦!

算法2:

在算法1的基础上,我们对每条边处理一下xor,就有20分啦!

算法3:

简单的树形DP,或者你会nlogn的dij,处理完每个点到其它点的最短路后再加上xor,那么这样就有30分啦!

算法4:

第4、5个点无需xor,那么我们树形DP扫一个节点与其它所有节点的路径长度之和,可以合并信息,最终均摊O(1),50分到手。

算法5:

第6个点xor 1,那么我们树形DP到一个点时记录有多少个0,多少个1,然后每当一条路径到2,那部分就再记录一个值,60分到手。

算法6:

如果你第6个点都过了,却没有满分,笨死啦!

一样的嘛,就是原来的“0”、“1”、大于等于2变成了0~16么~~

满了。

 

  • PoPoQQQ2015年4月1日 下午8:40 回复

    [捂脸熊]然后我过了前6个点,却没有AC,真是笨死了QAQ

    #1  
  • NULL2015年8月29日 上午11:54 回复

    ym

    #2  
  • 小奇的仓库 | Codeba2017年9月23日 下午12:52 回复

    […] 题目来源:hzwer […]

    #3