给定一棵节点数为$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$ 后的直径有两种情况：

• $mx[u]+mx[v]+1$
• $\max(len[u],len[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$相同。下面通过构造证明这个必要条件也是充分的。