D
有一颗 $N$ 个顶点的树，顶点依次标号 $1\sim N$ ，第 $i$ 条边连接着顶点 $A_i$ 和 $B_i$ ，且第 $i$ 条边的长度为 $C_i$ 。有一张 $N$ 个点的完全图，图上两点之间的边的边权为它们在树上的距离。求最长 $\text{Hamilton}$ 路径（即不重不漏恰好经过每个点一次）。
求 $\text{Hamilton}$ 路径转化为求 $\text{Hamilton}$ 回路再减去一条路径
对于 $\text{Hamilton}$ 回路，有一个结论：对于每一个边，把它断开后树分成了连通块 $x,y$ ，则有 $\min(x,y)$ 条路径通过该边
对于减掉的那条路径：
需要发现：不经过重心的路径都不会被包含在任意最优解中
那么每一条路径都是在重心的两个不同子树中各任取一点相连，于是，当重心为点时，删去以重心为端点的最短的一条边，重心为边时，删去那条边
E
给定平面上三个矩形：$[X_1,X_2]\times [Y_1,Y_2] ; [X_3,X_4]\times [Y_3,Y_4] ; [X_5,X_6]\times [Y_5,Y_6]$ ，在三个矩形中各选一个整点 $A,B,C$ ，再选择一条 $A\rightarrow B$ 的 $HV$ 格路以及 $B\rightarrow C$ 的 $HV$ 格路 ，求方案数
先考虑只有两个矩形，统计 $A\rightarrow C$ 的 $HV$ 格路数：
固定 $i,j,u$ 能进行上指标求和：
同理，对其他三个均进行上指标求和，得：
再考虑三个矩形：
假设固定了 $(x,y)\in [X_3,X_4]\times [Y_3,Y_4]$ ，那么只需对左下和右上方的矩形分别做一个二维部分和，同上转化出四个二项式系数
将问题看成：左下角的矩形集合可以等价于 $4$ 个 (带权的) 点，每个点有系数 $±1$ ，同理，右上角的矩形也可以等价于 $4$ 个 (带权的) 点，每个点有系数 $±1$
由此，原问题转化为 $16$ 个问题：给定起点 $(x_L,y_L)$
，终点 $(x_R,y_R)$ 和一个中途矩形 $[x_3,x_4]\times [y_3,y_4]$ ，求有多少种方案在中途矩形中选择点 $P$ ，以及一条 $(x_L,y_L)\rightarrow P$ 的 $HV$ 格路和一条 $P\rightarrow (x_R,y_R)$ 的 $HV$ 格路
首先考虑经过矩形 $[x_3,x_4]\times [y_3,y_4]$ 的格路数量：注意到任何一条经过某个矩形的格路至少经过这 $(x_4-x_3+1)+(y_4-y_3+1)$ 条边之一
那么枚举经过的这条边，后计算该边终点到 $(x_R,y_R)$ 的 $HV$ 格路数
而需要经过矩形中特定点的格路数，那么对于经过矩形的每一条格路，经过矩形内 $c$ 个点就会对最终方案数贡献 $c$
转化为求每条经过中途矩形的格路在中途矩形内长度之和：设到达时坐标 $(x_a,y_a)$ ，离开时 $(x_b,y_b)$ ，该格路在中途矩形内的长度就是 $(x_b-x_a)+(y_b-y_a)+1$
由于枚举起点终点，对上式求和会达到无法接受的 $O(n^2)$
这里考虑用分离变量：即，把 $(x_b-x_a)+(y_b-y_a)+1$ 拆成 $(x_b+y_b+1)-(x_a+y_a)$ ，然后在起点终点处分别统计并将贡献相加即可
再把该子问题做 $16$ 遍就好了
F
给定两个 $n$ 个点的树，给每个点赋值满足两棵树上均有任意节点子树权值和为 $1/-1$
先考虑一棵树情况
直接从叶子往上构造。但为便于推广，找出一个等价过程
由于一个子树对父亲的 $Size$ 的贡献只有 $1/-1$ ，所以考虑给树边定向：儿子指向父亲代表贡献为 $1$ ，反过来代表贡献为 $-1$
由于整个树的权值和也为 $1$ 或 $-1$ ，所以新建一个根 $0$ ，然后 $0$ 连向当前根，对 $0$ 点的定向就是整棵树的贡献
由此：先给所有边定向(随机即可)，对于一条儿子指向父亲的边，把儿子 $+1$ ，父亲 $-1$ ，这样只有以儿子为根的一个子树的大小改变，反之同理
实际上就是定向完后，$a_i=out_i-in_i$
两棵树
考虑此时如何保证对两棵树定向后的 $a_i=b_i$ ，考虑再加一些边
首先，如果两棵树上某个标号对应的两个点的度数奇偶性不一样，那么一定无解
其次，如果度数为奇数，就把这两个点连起来
这样得到的新图满足，连通（两个 $0$ 节点之间一定有连边），而且所有点度数均为偶数，即，存在欧拉回路
由欧拉回路的性质，对任意点 $in=out$
那么如果按照欧拉回路去定向，每个点的点权就都为 $0$ ，那么显然相等