caioj 1107
二叉树树形DP，设$dp(u, a)​$为$u​$节点所为根的子树保留$a​$条树枝的最优值
则 $dp(u, i) = max(dp(lc, i - j - 2) + dp(rc, j) | 1 \leq i \leq Q, 0 \leq j \leq i - 2)$(减二是因为要连接这两个子树所需要的代价)
初值$dp(u, 0) = 0$，最后的答案就很显然了

Codeforces 854D
题意：有n+1个城市，每个城市都有一个人，他们要去0城市参加活动，一起待k天，然后再回来，你可以提前去也可以延后回去，问 你能不能使所有人一起待k天，可以的话，最小花费是多少？

我们维护两个前缀和数组$l_i, r_i$，分别表示$i$前面的航班可以使得所有人到达0城市的最小费用、$i$后前面的航班可以使得所有人回去的最小费用，计算直接再开个数组记录各个城市的最小值即可。
然后答案可以合并，是$max(l_i+r_j)$，其中$j$是离$d_i+k+1$天最近的航班。
因为有可能回去的$r_i$对应的航班$i$是到达0城市的航班，中途被我continue了(其实其他方法可以避免)，使得单调性被破坏，我们可以进行恢复单调性(看代码注释部分)，所以直接找 离$d_i+k+1$天最近的航班 就是当前最优解。用二分找较为合适，复杂度$O(nlogn)$

Codeforces 855B
题意：给一个数组，求$p \cdot a_i + q \cdot a_j + r \cdot a_k$的最大值$(1 \leq i \leq j \leq k \leq n) $
维护前缀后缀最大值/最小值，然后我们枚举中间值$j$，算每个$j$作为中间点的值
然后$q$的贡献为$q \cdot a_i$
而对于$p$, 如果有$p \geq 0$，那么$p$的贡献为$p \cdot lmax_i$，反之$p$的贡献为$p \cdot lmin_i$
对于$r$, 如果有$r \geq 0$，那么$r$的贡献为$r \cdot rmax_i$，反之$r$的贡献为$r \cdot rmin_i$
然后最后可以得出一个最大的值，即为答案

Codeforces 864D
题意：给出一个n，以及n个数，这n个数范围为1~n。 现在问最少改变几个数能使这n个数成为1~n的排列，若有多种情况，使排列的字典序最小。

第一问就是不在给的序列中的数的个数，第二问我们考虑贪心。
要使得字典序最小，那就得让前面的元素尽量小。我们把不在序列中的数全部由底至上从大到小放到一个栈里(或者小根堆)，然后我们对于重复出现的元素，一定要修改，但要留下一个。那么我们考虑留下哪一个就好了。
顺序扫一遍如果当前元素还能被替换(个数大于1), 那么如果当前栈顶比当前元素小，那就直接替换(替换时要出栈以及个数减一)；反之就要跳过这个数不修改(只能跳一次，因为是要构成排列)。这样得到的序列一定是字典序最小的。

Codeforces 854C
题意：有n架飞机，第i架飞机原本计划在第i分钟起飞，可是由于某种原因整个机场前k分钟是不能起飞的，每分钟只能起飞一架飞机，然后告诉你每架飞机每延误一分钟会造成的损失，问你如何安排飞机的起飞时间才能将损失降到最少（飞机不能提前起飞）。

把所有飞机的延迟时间按照当前时间一一插入，然后每次起飞就飞延迟时间大的那个，因为越往后拖越损失大。

这题好多种方法……Orz各路神仙

我先想到的是删与 1 和 n 点都连通的点，然后 Tarjan 缩点之后，枚举每个原图点作为买入点，然后维护和这个点连通的点(scc)权值最大值，减一下就行。
删点 DFS 标记一下，不过要建反图。和这个点连通的点(scc)权值最大值可以用 DP 求得，直接记忆化搜索一下。

然后第二种做法是做两次最短路松弛找到每个点$i$的$1,i$最小值，$i,n$最大值，之后枚举点更新即可。

第三种做法是 DFS。我们发现就只有三种情况，1、找一个点买，2、找一个点卖，3、到终点。
所以每次 DFS 三种情况，用数组可以判重。

第四种做法是 BFS。和DFS差不多。也可以 DP 思想跑 BFS。

第五种做法是 分层图最短路。这里 fy1234567ok 的思路，非常好，也就是把原图分层3个层，第一层是寻找买入点，第二层是寻找售出点，第三层是寻找n点。中间连边代表操作。对于没有贸易活动，直接连到超级n点处。

Codeforces 844C
题意：给你一个序列，这个是序列是乱序的，你需要把它给排序，你有k个桶，每个数放入桶以后就会自动排序，然后再把这些数按原来的位置按现在的顺序放入，使得这个序列变得有序。问最大的k为多少？

先对原数组进行离散化，然后就得到一个1到$n$的排列。每个数要排到相应为位置(即$i=a[i]$)，那么我们逐位DFS，每次DFS到该位上的数值。因为$i$位置上的数$a[i]$是要被操作到$a[i]$位置上的，所以这次选的桶必须要选择$a[i]$。然后到了$a[i]$位置按照此过程继续走，直到之后走到的位置之前走过，就能停止了，这时只需要输出所有经过的节点就行，用set存比较好，自动拍好了序。由于操作次数要第一行输出，所以要用$n$个vector存答案，具体看代码的实现。

Codeforces 842D
题意：给你$n(n \leq 3 \times 10^5)$个数，有$m(m \leq 3 \times 10^5)$次询问，每次询问给一个数$x$，要你把整个序列所有数都与$x$异或，然后取$mex$值

考虑Trie树维护序列中每个数的二进制形式值，从左到右由根到叶子插入(比如插入$(100)_2$先插入1边再插入0边)。考虑设一个最大深度$MNL$，所有数的二进制位数都要为$MNL$，不足在左边补0。$MNL$的大小必须大于所有数二进制形式长度。
之后我们就得到了一棵维护二进制数的Trie。先不管异或，我们来谈谈$mex$的求法。
这是一个贪心过程，因为首位越小数字越小，所以在Trie树中找最小的不存在的数即可以从根开始往下走，如果能走0边，就走0边。不能走的情况是，0边这个方向的子树大小是满的，不会有空，所以子树下的都在集合中，不是$mex$，那么就往1边走。如果向下走出现了没有节点可走，那么下面就直接全部选0边(这里的0边都是不存在的)往下走即可。
由于xor满足右结合，$a$异或$b$异或$c= a$异或$(b$异或$c)$。那么我们每次询问只需要把前程的所有$x$异或起来得到$nx$就行了。
字典树怎么异或？很麻烦，时间也不保证。我们尝试不修改字典树来进行查询$mex$
对于$nx$，如果要求得原序列以后的$mex$，从根向下遍历，类似不异或的情况。但是选边尽量要选和$nx$二进制下的边相同的。因为这样异或以后就是0。然后每次询问就可以了，类似不异或的情况

Trie维护二进制很常用！

Codeforces 842C
题意：给定一棵树和它各个点的权值，对于一个结点它的美丽值是指他到根的路径上所有点权值的最大公约数，对于每个结点到根的路径，可以修改一个点的权值到0，问每个点的最大美丽值

树上暴力即可。暴力每个点改0的情况。
进行DFS，维护$now$(根到路径上所有数的$gcd$), $p$($u$的父亲), $s_u$($u$的集合(答案集合))
如果当前节点不改0，则当前节点可以和前面改过0或者没改过0的答案结合
如果当前节点改0，则当前节点只能和前面没改过0的答案结合($now$的作用)

然后之后输出$s_u$最后一个元素($set$内自动从小到大排序)即可

由于每个数的因子是分散的$\sqrt n$个，所以几个数的$gcd$很快变$1$，即$set$内元素个数不多，所以能很快算出答案

模板及讲解

字典树

字典树是前缀树，支持$insert(s)$和$query(s)$操作
两个函数按照树结构往下走处理即可

维护二进制 (Xor)

poj 3764

给定一棵$n$个点的带权无向树，求树上路径异或和的最大值。

利用 Xor 性质，我们发现路径异或和满足容斥 (即$[l,r]$可由$[1,r]，[1, l-1]$得出)
那么我们求根到每个点的异或和$d_i$，然后尝试如何异或出一条路径来
我们发现任意两个$d_i,d_j$的异或和为某条路径的异或和，且不漏解
那么问题转化为求序列$d_i$两两异或最大值。
因为 Xor 常用 Trie 维护，所以我们可以运用 Trie 求这个最大值。将所有$d_i$以二进制形式插入 Trie (高位在上，定一个最大位数，不够在前面补0)，边权为二进制位，然后对于每个二进制下的$d_i$在Trie树上走尽量相反的边，因为这样保证异或后大。树上没有最优边那就只能走另一条边。这样下来的路径就是$d_i$与其他$d_j$的最大异或值。$O(n \cdot len)$操作即可，$len$为二进制最大位数。

Codeforces 842D

常见题型

Trie树：
1、前缀问题
2、翻转字符串，处理后缀 jzoj 5397，bzoj 4567
3、01Trie：Xor问题 CF 842D，poj 3764
4、回文相关：Bzoj 1524 (多个回文串拼接问题)
Trie图：AC自动机
Fail树：bzoj 2938
前缀关系树 (Trie树去除虚节点) bzoj 4567