HNSDFZ2016 #1

A. ZY的钻石树 (Link)

时间限制: 1s / 内存限制: 250MB

题目描述

ZY是一个很神的孩子，对于他来说一切都是O(1)的。
ZY也是一个很喜欢玩MC的孩子。
这天，ZY登陆了他的MC，他发现他家不知道被哪个熊孩子糟蹋了。
他的家变成了一颗有N个节点的树，每个树都有一种钻石块(种类是1-1000000的整数表示)。
奇怪的是，同种的钻石块ZY只能拿一个。
更加奇怪的是，不同时刻某些钻石块还会改变自己的种类。
ZY因此想知道，以某个节点为根的子树中有多少个不同的钻石块
1号节点为树的根
两种操作：
1 x 询问x节点为根的子树有多少个不同的钻石块
0 x val 修改x节点的钻石块种类为val

输入格式

第一行N，代表树的节点数 第二行N个数，代表每个节点的钻石块种类 然后N-1行代表哪两个点连接 一行M代表操作数 之后M行代表操作

输出格式

对于每个询问输出其答案

样例输入

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

7
1 2 3 4 5 6 7
1 2
1 7
2 3
2 6
3 4
3 5
10
1 5
0 7 22
1 2
0 6 10
0 4 2
0 4 45
1 5
1 2
0 2 12
1 1

样例输出

1
2
3
4
5

1
5
1
5
7

数据范围及提示

m,n<=100000

B. ZY的核电站 (riteme)

时间限制: 5 s / 内存限制: 256 MB / 打开O2优化

题目描述

“ZY喜欢玩核电站。”

ZY的核电站非常特殊。早在2038年，ZY就发现了高分子有机物的完全裂解可以释放大量的核能的原理（这句话纯属FP）。因此ZY的核电站反应堆里面全是高分子有机物，可惜只有一个。
为了使发电量尽可能大，ZY找到了一种能使有机物完全裂解的方式，使释放出来的能量最大。由于这是ZY的有机物，因此裂解方式也非常奇葩。下面是ZY在2039年的论文《论ZY对MC¹核电站的巨大贡献》中的节选片段：

......
我们的有机物是由$n$个各种原子构成的，原子之间通过不同的共价键相连。

($\text{H}$太多了，到时候这些没用的氢原子都会被ZY丢掉)
......
为了方便进行裂解，这个有机物是没有环的，这样就可以节约成本来买**V*P***......
......
每次裂解都会断开一个共价键，此时这个有机物会分为两部分。并且释放大量的能量......
设放出的能量为$E$，有机物裂解后的两部分的共价键的集合分别为$A$和$B$，则：、
$$ E = \sum_{a\in A} a.\text{energy} \cdot \sum_{b\in B} b.\text{energy} \tag{ZY's energy theorem}$$

其中$\text{energy}$表示共价键的能量。
......
为了充分利用有机物中的能量，每裂解一个共价键后，我们有办法无损耗无成本的将其还原，即有机物会变得和裂解前一样。但是出于种种原因，这个共价键就不能再次进行裂解了。除非ZY发出SB之神力来使所有的共价键复活......
......
那么，一个有机物完全裂解所能放出的能量为所有共价键裂解一次后所放出的能量之和。
......

(实际上，ZY的这篇论文长达$2147483647$字)

当然，ZY的智商理论上为$-\infty$。因此它的核电站其实非常辣鸡。反应堆中的有机物不一定是稳定的，但是ZY利用LCT算法以$O(\infty!)$的时间复杂度内成功地保证了有机物的结构，这样就方便ZY发出SB之神力。但是令ZY想跳楼的是，总有一个共价键的能量在维护有机物结构时会变动。然而”机智”的ZY可以发现这些变化。
ZY只希望能够快速算出当前的有机物通过完全裂解究竟能放出多少能量。由于ZY的数学只有学前班水平，所以每当她算到一半时，这个有机物又开始乱搞了，ZY就只能用LCT来重新维护它。
一年之内，ZY的核电站什么电都没有发。为了快速计算，ZY找到了你这个**。
ZY希望你能给出一个好方法来帮助她计算当前有机物完全裂解能放出的能量。

输入格式

第$1$行输入两个正整数$n$，$m$。$n$表示有机物中原子的数量，$m$表示ZY维护有机物结构的次数。
接下来$n - 1$行描述一个有机物。对于每一行输入三个整数$u$，$v$和$e$，表示第$u$号原子和第$v$号原子之间以能量为$e$的共价键相连。
接下来$m$行，每一行描述一个共价键的键能变化。每行输入三个整数$u$，$v$和$e$，表示第$u$号原子和第$v$号原子之间的共价键的能量变为$e$。保证第$u$号原子和第$v$号原子之间存在共价键。

输出格式

对于每次共价键能量的变动，输出一行一个整数，表示键能改变后的有机物完全裂解能放出的能量。

输入样例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

7 4
1 2 2
1 7 1
2 3 2
2 6 1
3 4 1
3 5 1

1 2 2
1 2 3
2 3 3
1 2 0

输出样例

1
2
3
4

13
15
16
10

数据范围及提示

对于第一个询问:
裂解$1$和$2$之间的共价键: $1 \times (2 + 1 + 1 + 1) = 5$
裂解$2$和$3$之间的共价键: $(2 + 1 + 1) \times (1 + 1) = 8$
其余的共价键裂解得到的能量均为$0$。
因此答案为$13$。

对于$10\%$的数据: $n \le 1,000, \; m \le 5,000$
对于$10\%$的数据: $n \le 10,000, \; m \le 500,000$
对于$10\%$的数据: $n \le 100,000, \; m \le 100$
对于$10\%$的数据: $n \le 10,000, \; m \le 1,000,000$
对于另外$20\%$的数据: 有机物没有支链。
对于$100\%$的数据: $n \le 200,000, \; m \le 1,000,000, \; e \le 10 $

C. ZY的仙人掌 (blue)

时间限制: 2 s / 内存限制: 512 MB

题目描述

ZY是个很喜欢打MC的孩子，动态仙人掌对他来说是$O(1)$的。
ZY登录MC，发现自己在一个仙人掌包围的巨大盒子里。这是$n\times n$的巨大网格，可以走到上下左右相邻的格子，但是不能斜走。
ZY认为，既然来了，就要潇洒走一回。他tp到一个网格，准备步行前往另一个网格。
但是blue显然不愿意看到ZY如此悠闲。所以，每次ZY作出计划，blue都会让某个格子长出仙人掌。（ZY怎敢踏过仙人掌）

那么问题来了：给出ZY的计划和blue的操作，询问ZY能否完成计划。

输入格式

第一行，两个整数$n$、$m$，表示盒子是$n\times n$的，ZY有$m$个计划。 接下来$m$行，每行三个点对：$(x_1,y_1)$表示ZY的出发点，$(x_2,y_2)$表示ZY的目标点，$(x_3,y_3)$表示blue让这个点长出仙人掌。

输出格式

输出共$m$行，描述ZY的计划能否完成。 如果能完成，输出Yes，否则输出No

样例输入

1
2
3
4

5 3
1 1 4 4 2 2
1 1 3 3 1 2
1 1 3 3 3 1

样例输出

1
2
3

Yes
Yes
No

数据范围及提示

数据有梯度，暴力可拿分。

可能在同一个地点长仙人掌；也可能ZY从仙人掌出发或者到达仙人掌。如果遇到这种情况，请直接输出
No
n <= 1000 ?

D. ZY的三元组 (blue)

时间限制: 1 s / 内存限制: 233 MB

题目描述

ZY是个很神的孩子，计算勾股数对他来说是$O(1)$的。

对于 $a,b,c \in Z^+$，且$a<=b<=c$ 有 $a^k+b^k=c^k$，而且$a:b:c$为最简整数比，并且$c-b$不超过3，则称三元组$(a,b,c)$为贼达k拉斯三元组。

给定$n$和$m$，字典序输出所有$c<=n$，$2<=k<=m$的贼达k拉斯三元组。

输入格式

一行，$n,m$

输出格式

每行一个贼达k拉斯三元组。 如果没有就不输出.

样例输入

1

100 3

样例输出

1
2
3
4
5
6
7
8
9

3 4 5
5 12 13
7 24 25
8 15 17
9 40 41
11 60 61
12 35 37
13 84 85
16 63 65

数据范围及提示

数据范围
$n<=100000$，$2<=k<=1000$。

题解

A (Missing)

B

题目描述不用看，看样例就好了…
给你一棵无根树，每条边有边权。将一条边断开会出现两棵树，这两棵树的各自的边权之和相乘就是裂解一次的能量。完全裂解就是每一条都这样计算一下。
如果只要计算一次，考虑将无根树转为有根树，然后DFS一遍计算以每个节点的子树中的边权之和。根节点的这个值就是总边权之和。用对于每条边，用深度较大的节点来记录这条边上的信息$a$和$b$。$a$表示子树中的边权之和，$b$表示子树外的边权之和(当然要除去这条边)。然后在$\Theta(n)$的时间内可以计算出答案。
接下来考虑维护答案。对于每条边的修改，自己的$a$和$b$不会有影响，对于从这条边到根节点的链上的每一条边的$a$值都会增加，而对于其它的边的$b$值都会增加。因此我们用$\Delta a$和$\Delta b$来记录每一条边的增量，这个值可以利用树链剖分+线段树来维护，链上的边直接增加，其它边先全局打上标记，然后对不需要的边打上反标记即可。
最后在线段树的根节点统计答案，利用求和的性质即可：
$$ \begin{aligned} \sum^n_{i=1} a^,_i b^,_i & = \sum^n_{i=1} (a_i + \Delta a)(b_i + \Delta b) \\ & = \sum^n_{i=1} a_ib_i + \Delta a\sum^n_{i=1}b_i + \Delta b\sum^n_{i=1} a_i + n\Delta a\Delta b \end{aligned} $$
从这也能看出维护三个和式和两个标记就可完成维护。总复杂度为$O(n\log^2n)$。

C (Missing)

D (Missing)