P2056 [ZJOI2007] 捉迷藏 / abc460_f - Farthest Pair Query
前置结论
为了解决这个题，我们需要先证明一个重要结论：
定理1
设 \(T_1,T_2\) 为两棵树，直径分别为 \((a_1,b_1),(a_2,b_2)\)，设 \(T= T_1 \cup T_2\)，表示对 \(T_1,T_2\) 两个树中两个点集求并后，得到的新点集构成的树，则 \(T\) 的直径 \((x,y)\) 一定满足 $x,y \in {a_1,b_1,a_2,b_2} $。
证明
分两种情况讨论
情况1：\(x,y\) 都在 \(T_1\) 或 \(T_2\) 内
非常显然的，整棵树的直径就是 \(T_1/T_2\) 的直径，于是结论显然成立。
情况2：\(x,y\) 不在一个树内
不妨设 \(x\in T_1,y\in T_2\)
这个不太好严格证明，这里给出一个不是特别严谨的证法。
设 \(x \rightarrow y\) 路径上的两个点分别为 \(z_1,z_2\)，使得 \(z_1 \in T_1, z_2 \in T_2\)。
把 \(T_1,T_2\) 分开考虑。在 \(T_1\) 中，由于 \(x \rightarrow z\) 是直径的一段，\(x\) 一定是到 \(z_1\) 最远的点。这个正确性非常显然，如果不是最远那么肯定存在更长的直径方案。
由直径的性质，树上到任意一个点距离最远的点一定是直径的端点，于是可得 \(x \in \{a_1,b_1\}\)。
对 \(T_2\) 同理可得 \(y \in \{a_2,b_2\}\)。于是原命题成立。证毕。
与这个定理类似的，我们有两个关于树的直径的小结论，在此补充上：
定理2
设 \(T\) 为一棵树，其直径为 \((a,b)\)。现在向里面加一个叶子 \(p\)，则得到的新树 \(T'\) 的一条直径一定是 \((a,b),(a,p),(b,p)\) 之一。
证明
把一棵树的直径当做树的主链，如下图：
现在的树可以看成由主链和分叉组成。
如果 \(p\) 连在主链的两头，则原命题显然成立。
再处理 \(p\) 连在分叉上的情况。考虑反证法，假设存在 \(x \notin \{a,b\}\) 使 \(dis(p,x)>dis(a,p)\)。
拆解路径可得
因为 \((a,b)\) 是 \(T\) 的直径，所以由直径定义可得 \(dis(x,b) \le dis(a,b)\)，同样拆解路径得 \(dis(x,y)\le dis(a,y)\)。
于是发现与假设矛盾，假设不成立，则原命题成立。
虽然说，这个定理可以算是定理1的特殊情况，但树的直径题目中，把直径摘出来做长链不失为一种常用的思路，因此也需要了解。
这个定理还可以推广到用一条边连接任意两棵树的情况。
定理3
设 \(T_1,T_2\) 两棵树的直径分别为 \((a_1,b_1),(a_2,b_2)\)，现在用一条边 \((u,v)\) 连接两棵树，则新树 \(T\) 的直径 \((x,y)\) 一定满足 $x,y \in {a_1,b_1,a_2,b_2} $。
证明
这与定理1也没有什么本质区别，用相似证法很容易证出来，这里不再细讲。
解题思路
有了上面的结论，问题就迎刃而解了。
定理1告诉我们可以做到快速合并两棵树的直径。所以，我们考虑使用线段树，维护点编号在一定区间 \([l,r]\) 内的子树的直径长度和两个端点。pushup时，把左右子树的端点两两配对分别求路径长度，取最大值即可。
求路径长度，我们需要求出lca。常规方法是用树剖和树上倍增，但这两种方法的缺点是相同的，它们的查询自带一个 \(\log\)。
我们现在得到了 \(O(Q \log^2N)\) 复杂度的算法。虽然此题时限开得很大不会TLE，但如果放在csp-s常见的1s时限下，除非CCF少爷机发力，否则很难通过 \(5 \times 10^5\)。
于是我们有了下面的求lca科技：dfs序。它可以利用st表，在 \(O(N \log N)\) 时间的预处理后，\(O(1)\) 在线查询lca。
于是算法的瓶颈被我们优化掉了一个 \(\log\)，这便可以很轻松地通过此题。
DFS序求解lca
写在前面：事实上由于树剖的常数过于优秀，经测试理论上少一个 \(\log\) 的dfs序lca并没有比树剖的效率高多少，基本不相上下。
听说有个欧拉序求lca，复杂度没快时空常数还多一个2？听说还有人欧拉序没开两倍导致挂分？
前面已经说过，dfs序算法的原理是通过把lca转化为st表后，用st表算法求解得到lca，那它是怎么做到如此神奇的转化的呢？我们不妨看一张图：
不妨设 \(dfn[x]<dfn[y]\)，我们考虑时间戳 \(dfn\)在区间 \([dfn[x],dfn[y]]\) 的点，也就是上图中蓝色的点。
那么不难发现，lca就是蓝点中深度最小的点的父节点。这个不好严谨证明，感性理解即可。
于是lca就转化为了求区间中深度的最小值，直接跑st表板子。
那有人就问了，下面的情况你怎么办：
问题1：\(x\) 为 \(y\) 的祖先时，应当返回 \(x\)，但我们求出的结果为 \(fa[x]\)
这确实是个问题。为了避免这种情况，我们舍弃区间的左端点，把查询区间变成 \([dfn[x]+1,dfn[y]]\)。容易发现这样改既可以解决 \(x\) 是 \(y\) 祖先时出现的问题，也不会影响到 \(x\) 不是 \(y\) 的祖先时的求解。
问题2：\(x=y\) 时怎么处理
很简单，直接特判即可。
于是整个算法的流程就清晰明了了。首先跑出时间戳和深度，然后预处理st表，之后套用st表板子查询 \([dfn[x]+1,dfn[y]]\) 中深度的最小值即可，注意最后别忘了找父亲节点。
发现算法仍然需要维护深度和每个点的父节点，并没有起到优化空间常数的效果。
考虑等价转化。我们非常容易困难地注意到，lca也可以表示成时间戳在 \([dfn[x]+1,dfn[y]]\) 的点的父亲中，\(dfn\) 最小的点。
换句话说，用一个数组 \(F[i]\) 表示 \(dfn\) 值为 \(i\) 的点，它的父节点的 \(dfn\) 值是多少。注意前后两个值都是 \(dfn\)，千万不要理解成节点编号。
我们要做的，就是寻找 \(F\) 数组在 \([dfn[x]+1,dfn[y]]\) 中的最小值，还是用st表，但不需要维护额外的东西了。我们成功的省下了空间，减小了时空常数。
下面给出本题树剖和dfs序的两份代码。不得不提的是，由于树剖的常数过于优秀，导致洛谷上测出两种方法差距很小。在板子题上测dfs序还是快一些。
所以考场上忘了dfs序大胆写树剖一般也没事，但一定不要写普通倍增，这个东西真的很慢！！！
树链剖分
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;const int N=1e5+10;
struct Node{int l,r,c,x,y,d;}tr[N<<2];
vector<int> g[N];
int siz[N], son[N], fa[N], Top[N], d[N];
int n,m,ans;void Dfs1(int u){siz[u]=1;for(int v:g[u]){if(v==fa[u]) continue;d[v]=d[u]+1; fa[v]=u;Dfs1(v);if(siz[v]>siz[son[u]]) son[u]=v;siz[u]+=siz[v];}
}void Dfs2(int u, int tp){Top[u]=tp;if(son[u]) Dfs2(son[u],tp);for(int v:g[u]){if(v==fa[u] || v==son[u]) continue;Dfs2(v,v);}
}inline int lca(int x, int y){while(Top[x]!=Top[y]){if(d[Top[x]]<d[Top[y]]) swap(x,y);x=fa[Top[x]];}if(d[x]>d[y]) swap(x,y);return x;
}inline int dis(int x, int y){return d[x]+d[y]-(d[lca(x,y)]<<1);
}inline Node Max(Node x, Node y){if(x.d>y.d) return x;return y;
}inline void pushup(int u){Node &t=tr[u], lc=tr[u<<1], rc=tr[u<<1|1];if(lc.x==0 || lc.y==0){t.x=rc.x; t.y=rc.y; t.d=rc.d;return;}if(rc.x==0 || rc.y==0){t.x=lc.x; t.y=lc.y; t.d=lc.d;return;}Node ans=Max(lc,rc);Node now={0,0,0,0,0,0};now.x=lc.x; now.y=rc.x; now.d=dis(now.x,now.y);ans=Max(ans,now);now.x=lc.x; now.y=rc.y; now.d=dis(now.x,now.y);ans=Max(ans,now);now.x=lc.y; now.y=rc.x; now.d=dis(now.x,now.y);ans=Max(ans,now);now.x=lc.y; now.y=rc.y; now.d=dis(now.x,now.y);ans=Max(ans,now);t.x=ans.x; t.y=ans.y; t.d=ans.d;
}void build(int u, int l, int r){tr[u].l=l; tr[u].r=r;if(l==r){tr[u].x=tr[u].y=l;tr[u].d=0;tr[u].c=1;return;}int mid=(l+r)>>1;build(u<<1, l,mid);build(u<<1|1, mid+1,r);pushup(u);
}void changly(int u, int x){if(tr[u].l==tr[u].r){tr[u].c^=1;if(tr[u].c==1){tr[u].x=tr[u].y=x;}else tr[u].x=tr[u].y=0;return;}int mid=(tr[u].l+tr[u].r)>>1;if(x<=mid) changly(u<<1, x);else changly(u<<1|1, x);pushup(u);
}signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n;for(int i=1; i<n; i++){int u,v; cin>>u>>v;g[u].eb(v); g[v].eb(u);}Dfs1(1);Dfs2(1,1);build(1,1,n);int q; cin>>q;while(q--){char ch; int x; cin>>ch;if(ch=='G'){if(tr[1].x==0 || tr[1].y==0){if(tr[1].x==0 && tr[1].y==0)cout<<"-1\n";else cout<<"0\n";}else cout<<tr[1].d<<"\n";}else{cin>>x;changly(1,x);}}return 0;
}
dfs序
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;const int N=1e5+10;
struct Node{int l,r,c,x,y,d;}tr[N<<2];
vector<int> g[N];
int f[21][N],dfn[N],lg[N],d[N];
int n,m,ans,cur;inline int Min(int x, int y){if(dfn[x]<dfn[y]) return x;return y;
}
void Dfs(int fa, int u){dfn[u]=++cur;for(int v:g[u]){if(v==fa) continue;f[0][cur+1]=u; d[v]=d[u]+1;Dfs(u,v);}
}
inline void st(){for(int i=1; i<=lg[n]; i++)for(int j=1; j+(1<<i)-1<=n; j++)f[i][j]=Min(f[i-1][j], f[i-1][j+(1<<(i-1))]);
}
inline int lca(int x, int y){if(x==y) return x;if(dfn[x]>dfn[y]) swap(x,y);int l=dfn[x]+1, r=dfn[y], k=lg[r-l+1];return Min(f[k][l], f[k][r-(1<<k)+1]);
}
inline int dis(int x, int y){return d[x]+d[y]-(d[lca(x,y)]<<1);
}inline Node Max(Node x, Node y){if(x.d>y.d) return x;return y;
}inline void pushup(int u){Node &t=tr[u], lc=tr[u<<1], rc=tr[u<<1|1];if(lc.x==0 || lc.y==0){t.x=rc.x; t.y=rc.y; t.d=rc.d;return;}if(rc.x==0 || rc.y==0){t.x=lc.x; t.y=lc.y; t.d=lc.d;return;}Node ans=Max(lc,rc);Node now={0,0,0,0,0,0};now.x=lc.x; now.y=rc.x; now.d=dis(now.x,now.y);ans=Max(ans,now);now.x=lc.x; now.y=rc.y; now.d=dis(now.x,now.y);ans=Max(ans,now);now.x=lc.y; now.y=rc.x; now.d=dis(now.x,now.y);ans=Max(ans,now);now.x=lc.y; now.y=rc.y; now.d=dis(now.x,now.y);ans=Max(ans,now);t.x=ans.x; t.y=ans.y; t.d=ans.d;
}void build(int u, int l, int r){tr[u].l=l; tr[u].r=r;if(l==r){tr[u].x=tr[u].y=l;tr[u].d=0;tr[u].c=1;return;}int mid=(l+r)>>1;build(u<<1, l,mid);build(u<<1|1, mid+1,r);pushup(u);
}void changly(int u, int x){if(tr[u].l==tr[u].r){tr[u].c^=1;if(tr[u].c==1){tr[u].x=tr[u].y=x;}else tr[u].x=tr[u].y=0;return;}int mid=(tr[u].l+tr[u].r)>>1;if(x<=mid) changly(u<<1, x);else changly(u<<1|1, x);pushup(u);
}signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n;for(int i=2; i<=n; i++) lg[i]=lg[i>>1]+1;for(int i=1; i<n; i++){int u,v; cin>>u>>v;g[u].eb(v); g[v].eb(u);}Dfs(0,1);st();build(1,1,n);int q; cin>>q;while(q--){char ch; int x; cin>>ch;if(ch=='G'){if(tr[1].x==0 || tr[1].y==0){if(tr[1].x==0 && tr[1].y==0)cout<<"-1\n";else cout<<"0\n";}else cout<<tr[1].d<<"\n";}else{cin>>x;changly(1,x);}}return 0;
}