https://qoj.ac/problem/9678一棵n点的树，你可以询问dis(u,v)+dis(v,w)+dis(u,w)（u,v,w两两不同）3n次，询问两次u是否在v到w的路径上。求任意一条直径的两端点。显然三个点的查询结果是三点间路径并的长度的两倍。找直径，要求从一个点出发找最远点。感知一下。固定一条

树V图相同\(f(i)\)的点必然构成一个连通块，不然一定无解。每一个连通块中需要选出一个关键点，考虑相邻连通块是否合法，发现条件其实很很好判，就是两个交界点的距离需要满足某个大小关系，容易预处理后\(O(1)\)判，于是\(f_{u,x}\)表示\(u\)连通块内取\(x\)的方案数，DP即可。

图中不存在横插边，\(u\rightsquigarrowv\)可拆成\(u\rightsquigarrow\operatorname{lca}(u,v)\rightsquigarrowv\)计算。对\(u\rightsquigarrow\operatorname{lca}(u,v)\)，不可能走第二类道路，树形DP统计每条边被经过的次数并累加答案即可，时间复杂度\(\mathcalO(2

NOIP2014奶酪题面：NOIP2014提高组D2T1现有一块大奶酪，它的高度为\(h\)，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为\(z=0\)，奶酪的上表面为\(z=h\)。现在，奶酪的下表面有一只小