[CTSC2018] 暴力写挂

两棵树，考虑枚举第一棵树的 LCA。

由于贡献是对称的，用 dsu on tree 把答案变成 \(O(n\log n)\) 个询问。

每个询问形如：查询第一棵树上 dfn 在一个区间里的点 \(p\in [l,r]\) 和点 \(u\) 在第二棵树上的 LCA 的深度和 \(p\) 的权值和的最大值。

可以在第二颗树上 DFS 的过程中维护每个点到当前 DFS 点的答案，需要矩阵加矩阵求和的操作。使用 KDT 维护，复杂度是 \(O(n\sqrt{n}\log n)\) 的，加上一些剪枝只能在原数据跑 85 分。

考虑拆贡献：两点 \((u,v)\) 的 LCA 的深度 \(d_{LCA}\) 相当于 \(\dfrac{d_u+d_v-dis_{u,v}}{2}\)。

于是可以在第二棵树上点分治，需要做单点修改，区间最值。使用线段树维护，常数不太大，复杂度是 \(O(n\log^3 n)\) 的，可以通过。

事实上不需要把询问离线下来。

在对第一棵树 dsu on tree 的过程中，可以在第二颗树上的点分树上直接维护信息。

由于是求最大值，点分树上每个点需要维护最大值和最大值的来源儿子，以及来源儿子不同于最大值来源儿子的最大值。

dsu on tree 的时候可以先递归轻子树，清空后递归重子树并继承信息。

不需要使用数据结构，时间复杂度 \(O(n\log^2 n)\)，可以通过;

另一类做法

对于两棵树的问题，有时候会采用点分治+虚树地解决方法。

本问题中，需要使用三度化边分治和虚树上换根 dp。

点分治是无法做的，因为度数较大，无法很好地处理不同子树间的情况。

没有写这种做法。