题目传送门
之前都在写洛谷冷门题目，今天来写一题AT的。
题目概述：F - Farthest Pair Query
- 问题背景：给定一棵包含 N 个顶点的无根树，顶点编号为 1 到 N 。初始状态下，所有顶点均被涂为黑色。
- 操作与查询：需要按顺序处理 Q 次查询。每次查询给出一个整数 x ，将顶点 x 的颜色进行翻转（黑变白，或白变黑）。翻转完成后，必须立即计算并输出当前所有黑色顶点中，任意两点间简单路径边数的最大值（即黑色点集的直径）。
- 数据范围：3≤N≤1e5 ，1≤Q≤1e5。时间限制为 4 秒，内存限制为 1024 MiB。
- 关键保证：题目明确保证在处理每一次查询时，树上的黑色顶点数量始终至少为 2 个。这意味着在编写代码时，无需特殊处理黑色顶点数为 0 或 1 时的边界返回
这里要求树的直径，求树的直径有三种方法：
1、两次DFS（BFS）：最常用，原理是通过从任意点X，搜到最远点u，再通过u找到最远点v，u和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(l==r){///当l=r时，就是叶子结点，直径为0 segtree[i]={l,r,0}; return; } int mid=(l+r)/2;///构建左、右儿子 build(l,mid,2*i); build(mid+1,r,2*i+1); push_up(i);///就是暴穷力举6种情况，将直径求出 }修改时从叶子结点修改（后根），一直修改到根（就是把白色点去掉再搜），时间为O(logN)。
void change(int l,int r,int x,int i){///单点修改，不用写区间 int mid=(l+r)/2; if(l==x&&r==x){///搜到这个点，开始向上反回 if(segtree[i].len==0)segtree[i].len=-1;///黑变白 else segtree[i].len=0;///白变黑 return; } if(x<=mid)change(l,mid,x,2*i);///继续向下搜索 else{ change(mid+1,r,x,2*i+1); } push_up(i);///暴力修改直径 }最后输出segtree[1]即可。
