题目链接:LOJ 3048
小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。
小粽面前有 $n$ 种互不相同的粽子馅儿,小粽将它们摆放为了一排,并从左至右编号为 $1$ 到 $n$。第 $i$ 种馅儿具有一个非负整数的属性值 $a_i$。每种馅儿的数量都足够多,即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 $k$ 个粽子。
小粽的做法是:选两个整数数 $l,r$,满足 $1\le l\le r\le n$,将编号在 $[l,r]$ 范围内的所有馅儿混合做成一个粽子,所得的粽子的美味度为这些粽子的属性值的异或和。
小粽想品尝不同口味的粽子,因此它不希望用同样的馅儿的集合做出一个以上的粽子。
小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧!
数据范围:$1 \le n \le 5 \times 10 ^ 5$,$1 \le k \le \min\left\{\frac{n(n - 1)}{2}, 2 \times 10 ^ 5\right\}$,$0 \le a_i \le 2 ^ {32} - 1$。
题目链接:LOJ 3052
距离苏拉威西只有一百公里了,车内的空气比窗外更加冰冷。四双眼睛紧盯着艾莉芬面前的屏幕,那是控制行星发动机的关键程序:春节十二响。他需要将其部署到电力控制系统的一个芯片中。
「春节十二响」由 $n$ 个子程序构成,第 $i$ 个子程序所需的内存空间是 $M_i$。这 $n$ 个子程序之间的调用关系构成了一棵以第 $1$ 个子程序为根的树,其中第 $i$ 个子程序在调用树上的父亲是第 $f_i$ 个子程序。
由于内存紧张,电力控制芯片上提供了一种内存分段机制。你可以将内存分为若干个段 $S_1, S_2, \dots, S_k$,并将每个程序预先分配到一个固定的段。如果两个子程序没有直接或间接的调用关系,则他们可以被分配到同一个段中,反之则不能。换言之,当且仅当 $a$ 和 $b$ 在调用树上不是祖先-后代关系,$a$ 和 $b$ 可以被分配到同一个段中。
一个段的大小应当是所有分配到这个段的子程序所需内存大小的最大值,所有段大小的和不能超过系统的内存大小。
现在艾莉芬想要知道,电力控制芯片至少要有多少内存,才能保证春节十二响的正确运行。即:最少需要多大的内存,才能通过先将内存分成若干个段,再把每个子程序分配到一个段中,使得每个段中分配的所有子程序之间不存在祖先-后代关系。
数据范围:$1 \le n \le 2 \times 10 ^ 5$,$1 \le M_i \le 10 ^ 9$。