题目传送门之前都在写洛谷冷门题目今天来写一题AT的。题目概述F - Farthest Pair Query问题背景给定一棵包含 N 个顶点的无根树顶点编号为 1 到 N 。初始状态下所有顶点均被涂为黑色。操作与查询需要按顺序处理 Q 次查询。每次查询给出一个整数 x 将顶点 x 的颜色进行翻转黑变白或白变黑。翻转完成后必须立即计算并输出当前所有黑色顶点中任意两点间简单路径边数的最大值即黑色点集的直径。数据范围3≤N≤1e5 1≤Q≤1e5。时间限制为 4 秒内存限制为 1024 MiB。关键保证题目明确保证在处理每一次查询时树上的黑色顶点数量始终至少为 2 个。这意味着在编写代码时无需特殊处理黑色顶点数为 0 或 1 时的边界返回这里要求树的直径求树的直径有三种方法1、两次DFSBFS最常用原理是通过从任意点X搜到最远点u再通过u找到最远点vu和v的距离就是直径这题用不了不详细说了。2、树形DP原理是通过以任意节点为根DFS 过程中对每个节点维护从其子树中延伸出的最长链和次长链。全局直径即为所有节点的最长链 次长链的最大值这题也用不了。3、分治法线段树LCA⭐本题使用线段树在这里指起到了存储的作用核心性质是若集合 A 的直径端点为 (a1,a2)集合 B 的直径端点为 (b1,b2) 则 A∪B 的直径端点一定在 {a1,a2,b1,b2}这 4 个点中产生。说白了就是把全集一分为二全集的直径在两个子集的直径的4个点的6个组合。这里为什么只能用分治法这里有单点修改用分治法只会影响包含该点的集合就是一条链其余方法都是影响所有要重新处理超时。思路构造线段树就是无白色点的直径时间约为O(4N)。void build(int l,int r,int i){///l~r,序号为i if(lr){///当lr时就是叶子结点直径为0 segtree[i]{l,r,0}; return; } int mid(lr)/2;///构建左、右儿子 build(l,mid,2*i); build(mid1,r,2*i1); push_up(i);///就是暴穷力举6种情况将直径求出 }修改时从叶子结点修改后根一直修改到根就是把白色点去掉再搜时间为O(log⁡N)。void change(int l,int r,int x,int i){///单点修改不用写区间 int mid(lr)/2; if(lxrx){///搜到这个点开始向上反回 if(segtree[i].len0)segtree[i].len-1;///黑变白 else segtree[i].len0;///白变黑 return; } if(xmid)change(l,mid,x,2*i);///继续向下搜索 else{ change(mid1,r,x,2*i1); } push_up(i);///暴力修改直径 }最后输出segtree[1]即可。