给定一棵节点数为$n$的树，每一条边有一个权值。现在要求从$1$号点出发，在不经过一个点超过$k$次的情况下经过的边的权值和最大。
设$f_{i,0/1}$为以$i$为根的子树中进去后回溯/不回溯的边权最大值，合并时将子树对应值排序即可，如果回溯的话只能从回溯的值里选，如果不回溯的话只能选一个不回溯的子树其它都要回溯，最后答案为$f_{1,1}$。
有一颗$n$个节点的树和$m$种冰淇淋，树上的第$i$个节点有$s_i$个冰淇淋，且所有相同种类的冰淇淋在树上构成了一个联通块。构造一个新的图$G$ ，$G$有$m$个节点，$G$中的$u$和$v$之间有边，当且仅当存在至少一个在树上的节点满足他同时有第$u$种和第$v$种冰淇淋。你的任务是用尽可能少的颜色种类数给$G$的每一个节点染色，使得没有两个相邻的节点有相同的颜色，要求输出方案。注意空的点集也被认为是一个联通块。
可以发现答案下界是数上节点中冰淇淋数量的最大值，因为这些它们对应的节点之间互相有边，可以发现这个下界是可以被构造出来的。以冰淇淋最多的点为根开始遍历，因为原图是一棵树，所以如果不回溯一个冰淇淋对应的连通块如果消失了那么它就永远不会出现，因此我们可以将它对应的颜色给另一种冰淇淋而不会冲突，使用set维护这一过程即可，注意回溯的时候要撤销，细节比较多。
给定一片森林，$q$ 此询问，每次给出两个点 $u,v$ ，如果 $u,v$ 在一棵树内输出 $-1$ ，否则在这两棵树任取一点临时建立一条边，求连边后的直径的期望。$(n,q\le 10^5)$
首先我们可以预处理出每个点在哪棵树中，其次预处理出每个点 $u$ 到这棵树叶子的最大值 $mx[u]$ ，这个可以用树形$DP$ 处理，将每棵树按照这个最大值进行排序，最后在处理出每棵树的直径长度 $len$ 。询问的时候枚举点数少的树，在另一棵树中寻找另一个点。将两棵树连接 $u,v$ 后的直径有两种情况：
第二种情况是一个定值，因此对于每一个 $v$ 我们可以二分出满足第一种情况的 $u$ 的个数，剩余的即为第二种情况。最后答案要用 $map$ 记录下来避免重复询问。复杂度是神奇的 $O(n\sqrt{n}\log{n})$
给你一棵$n$个节点的树，保证$n$为偶数，边权为$1$，问是否存在一个完美匹配，使得两两点之间距离之和恰好等于$k$。$(n \le 10^5, k \le n^2)$
我们考虑一条边，它将整棵树分为两棵子树，大小分别为$x$和$n-x$，两者奇偶性相同。所有两点位于两侧的匹配都会经过这条边，而其它匹配一定是在各自子树内完成的，因此这条边被经过的次数的奇偶性一定和$x$相同，同时也有一个显然的上界$\min(x,n-x)$，设该边贡献的权值为$a$，则有$(x \mod 2 )\le a \le \min(x, n - x)$。
我们以树的重心为根，那么除了根节点外，以每个节点为根的子树都小于另一部分，即$\min(x,n-x)=x$，因此对于每一条边我们可以得到公式$\sum (siz_i\mod 2) \le k \le \sum siz_i$，且$k$的奇偶性和$\sum siz_i$相同。下面通过构造证明这个必要条件也是充分的。
将根节点的每个子树中的点都和另一个子树匹配，总权值就是$\sum siz_i$，因为重心为根，每个子树大小不超过总体的一半，因此该匹配是存在的。现在我们可以通过如下的方案将总权值减少到不小于$\sum (siz_i\mod 2)$的任意与$\sum siz_i$奇偶性相同的值：
我们每次考虑根节点的各个子树，每次都考虑未匹配节点数最多的那个子树，我们每次将该子树中的两个点$x,y$进行匹配（而不是像上述所说各自匹配到根节点另外子树的节点），对最终权值的减少量为$2 \cdot dep_{\operatorname{lca}(x,y)}$，因此我们只需不断地寻找两个合适的点进行匹配，使得最终权值不断减少直到$k$。最后，因为我们每次都相当于让最大子树的节点数减少两个，因此根节点一直都是重心，最后只需将剩余点按dfn序排序，贪心地令$i$和$i+\frac{|v|}{2}$匹配即可（类似2020牛客第二场那题）。
具体实现过程我们只需要开个大根堆维护最大的子树，再开个set维护每个子树中存在一个及以上儿子的节点（不然没办法让它成为$\operatorname{lca}$）及其深度，并且每次优先选择最深的点删除即可。
给定一棵$n$个节点的树，每个节点有两个权值$a_i,b_i$，要求将树分为数条互不相交的链，每条边都必须被划分，点可以重复，且每条链的$a_i$单调（非严格单增或单减），求所有链的$b_i$之和的最小值。$(n \le 2 \times 10^5)$
先考虑所有边都各自成一条链，然后再对边进行合并从而减少答案。考虑给边进行定向，由$a_i$小的点指向大的点；如果两个点$a_i$相同那么边的方向任意，需要在后续dp过程中进行讨论。设$f_i$为以$i$为根的子树中若$i$与它父亲的边向下所能减少的最大权值，$g_i$为以$i$为根的子树中若$i$与它父亲的边向上所能减少的最大权值，$S_i$为节点$i$的子节点集合，那么有$$f_i=\max_{S\in S_i}(\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j+ b_i \cdot \min(|S|,|S_i|-|S|+1))$$ $$g_i=\max_{S\in S_i}(\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j+ b_i \cdot \min(|S|+1,|S_i|-|S|))$$ 前面的式子不好处理，我们可以化简得到$$\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j=\sum_{j\in S_i}g_j + \sum_{j \in S}(f_j-g_j)$$ 前者为定值，我们可以将子节点的$f_j-g_j$从大到小排序，设为$sum_i$，同时设$cnt_i$为节点$i$的子节点数，则有$$f_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j,cnt_i-j+1))$$ $$g_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j+1,cnt_i-j))$$ 最后根节点的答案特判一下，即为$$root_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j,cnt_i-j))$$时间复杂度$O(n \log n)$。
定义一个序列$[s_1, s_2, \dots, s_k]$的前缀前缀和为$s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k)$。
给出一棵$n$个节点的树，每个点有一个权值，求一条有向路径，使得每个点权值所构成的序列的前缀前缀和最大。$(2 \le n \le 150000)$
看到路径问题，直接上点分治，我们考虑两条路径合并时如何计算前缀前缀和。我们规定其它节点到分治中心的方向为向上，反之为向下。考虑所有向上路径对向下路径的贡献，设向上路径的前缀前缀和为$b$，所有节点权值之和为$x$，向下路径的前缀前缀和为$a$，节点数为$k$，则该路径的总前缀前缀和$y$为$$y=(kx+b)+a$$其中括号内是一个一次函数的形式而$a$是一个定值，因此问题转化为多个一次函数求横坐标为某一值时的最大值，直接使用LineContainer即可。
注意我们每条路径向上向下均有可能，因此每一个分治中心要进行两次，一正一反。另外分治中心我们并没有考虑，编写时无论将其放在向下或向上均可，还需要注意存在分治中心为一个端点的向上或向下的路径答案，不要忘记特判。