水题
Solution 1
首先这题可以加强成这样：
要求维护一个程序，执行下列操作：
- 若 u 和 v 不连通，在 u 和 v 之间加一条权值为 w 的边
- 若存在，删去 u 和 v 之间的边
- 查询点 u 连通块中离 u 最远的点
数据强制在线 。
（建议下次出到模拟赛里
通过这样的题面，我们就很容易想到解法了： lct 维护最大深度
（ ps ：后面的内容仅考虑边权为 1 的解法，边权不为 1 将维护的 siz 改成边权和即可 ）
首先，我们要在 lct 的节点上额外维护一个值 ：在 Splay 子树内深度最小的点往下的最大深度 mxf
由于 Splay / FHQ 要求支持 reverse 操作，所以我们还需要维护和 mxf 相反转移的 mxg
这样在 reverse 的时候我们只需要交换 mxf 和 mxg
我们考虑如何转移：
- 首先，显然 ，即最小点不经过 u
- 对于经过 u ，有一个转移是 ，即过 u 后进入右子树
- 还有一种情况是进入其他轻链，这时候需要我们维护一个可删堆 / set ，此时
其中 只需要在 access 和 Link 的时候注意维护即可
the code
基本就是模板，不理解的话可以照着代码和上文（绝对不是我懒得写注释
ps ： 这道题本来 lct 时限比较紧，然后我要了个管理员偷偷改成 2s 了
过不了的加 inline ， register ， 快读快写， 然后可以把 pushll 改成手写栈
或者你找 cls 再加一秒
#include<cstdio>
#include<cctype>
#include<queue>
#include<algorithm>
#define R register
using namespace std;
inline int read() {
R int x = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return x;
}
inline void write(int x) {
if (x > 9) write(x / 10);
putchar (x % 10 + 48);
}
const int MAXN = 200005;
int n, m;
int lu[MAXN], lv[MAXN];
typedef struct _heap {
private : priority_queue<int>me, del;
public :
inline int top() {
while (!del.empty() && del.top() == me.top()) me.pop(), del.pop();
return me.top();
}
inline bool empty() {
while (!del.empty() && del.top() == me.top()) me.pop(), del.pop();
return me.empty();
}
inline void push(R int x) {
me.push(x);
}
inline void erase(R int x) {
del.push(x);
}
} heap;
namespace Link_cut_tree {
#define lc sons[u][0]
#define rc sons[u][1]
struct node {
int siz, mxf, mxg, tg;
}tr[MAXN];
int fa[MAXN], sons[MAXN][2];
heap hp[MAXN];
inline bool isroot(R int u) {
return sons[fa[u]][0] != u && sons[fa[u]][1] != u;
}
inline void reverse(R int u) {
tr[u].tg ^= 1;
swap(lc, rc);
swap(tr[u].mxf, tr[u].mxg);
}
inline void push_down(R int u) {
if (!tr[u].tg) return;
tr[u].tg = 0;
if (lc) reverse(lc);
if (rc) reverse(rc);
}
inline void push_up(R int u) {
tr[u].siz = tr[lc].siz + tr[rc].siz + 1;
tr[u].mxf = tr[u].mxg = 0;
if (lc) {
tr[u].mxf = max(tr[u].mxf, tr[lc].mxf);
tr[u].mxg = max(tr[u].mxg, tr[lc].mxg + tr[rc].siz + 1);
tr[u].mxf = max(tr[u].mxf, tr[lc].siz);
}
if (rc) {
tr[u].mxf = max(tr[u].mxf, tr[rc].mxf + tr[lc].siz + 1);
tr[u].mxg = max(tr[u].mxg, tr[rc].mxg);
tr[u].mxg = max(tr[u].mxg, tr[rc].siz);
}
if (!hp[u].empty()) {
tr[u].mxf = max(tr[u].mxf, hp[u].top() + tr[lc].siz + 1);
tr[u].mxg = max(tr[u].mxg, hp[u].top() + tr[rc].siz + 1);
}
}
inline void Rotate(R int u) {
int fath = fa[u];
int g_fa = fa[fath];
int k = (sons[fath][1] == u);
fa[u] = g_fa;
if (!isroot(fath))
sons[g_fa][sons[g_fa][1] == fath] = u;
if (sons[u][!k]) fa[sons[u][!k]] = fath;
sons[fath][k] = sons[u][!k];
sons[u][!k] = fath; fa[fath] = u;
push_up(fath);
}
inline void pushll(R int u) {
if (!isroot(u)) pushll(fa[u]);
push_down(u);
}
inline void Splay(R int u) {
pushll(u);
R int fath, g_fa;
while (!isroot(u)) {
fath = fa[u]; g_fa = fa[fath];
if (!isroot(fath))
Rotate(((sons[fath][1] == u) ^ (sons[g_fa][1] == fath)) ? u : fath);
Rotate(u);
}
push_up(u);
}
inline void access(R int u) {
for (R int son = 0; u; u = fa[son = u]) {
Splay(u);
if (rc) hp[u].push(tr[rc].mxf);
if (son) hp[u].erase(tr[son].mxf);
rc = son;
push_up(u);
}
}
inline void makeroot(R int u) {
access(u); Splay(u);
reverse(u);
}
inline void Link(R int u, R int v) {
makeroot(u); makeroot(v);
hp[u].push(tr[v].mxf);
fa[v] = u;
}
inline void cut(R int u, R int v) {
makeroot(u); access(v);
Splay(u);
fa[v] = rc = 0;
push_up(u);
}
#undef lc
#undef rc
}
using namespace Link_cut_tree;
int main()
{
n = read(), m = read();
for (R int i = 1; i < n; ++ i) {
lu[i] = read(), lv[i] = read();
Link(lu[i], lv[i]);
}
int op, x;
while (m --) {
op = read(), x = read();
if (op == 1) {
cut(lu[x], lv[x]);
} else {
makeroot(x);
write(tr[x].mxf);
putchar('\n');
}
}
return 0;
}
Solution 2
既然是弱化版那就不用这么复杂
不强制在线，那么正难则反，将删边变成加边
有一个小 trick ： 加边后的直径在原两个连通块直径的四个点之间，证明显然
那么先在原树上 lca 求出两点距离，然后倒着做，合并的时候分讨一下即可
the code
我都说这么清楚了你就别看代码了吧
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 200005;
int n, m, cut[MAXN];
int a[MAXN], b[MAXN];
int dep[MAXN], fa[MAXN][25];
int ans[MAXN];
struct edge {
int to, nex;
}e[MAXN << 1]; int idx, head[MAXN];
inline void add(int u, int v) {
e[++ idx].to = v;
e[idx].nex = head[u];
head[u] = idx;
}
struct Dia {
int a, b, dis;
}d[MAXN];
struct Qry {
int op, x;
}q[MAXN];
namespace UNQ {
int fa[MAXN];
inline void Init (int n) {
for (int i = 1; i <= n; ++ i) fa[i] = i;
}
inline int Find(int x) {return (x == fa[x]) ? x : fa[x] = Find(fa[x]);}
inline void Merge(int u, int v) {
u = Find(u), v = Find(v);
fa[u] = v;
}
}
inline void dfs(int u) {
for (int i = 1; i <= 20; ++ i)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int i = head[u]; i; i = e[i].nex) {
int v = e[i].to;
if (v == fa[u][0]) continue;
dep[v] = dep[u] + 1;
fa[v][0] = u;
dfs(v);
}
}
inline int Lca(int u, int v) {
if (dep[u] < dep[v])
swap(u, v);
for (int i = 20; ~i; -- i)
if (dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if (u == v) return u;
for (int i = 20; ~i; -- i)
if (fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
inline int Get(int u, int v) {
return dep[u] + dep[v] - 2 * dep[Lca(u, v)];
}
inline Dia Mrg(Dia x, Dia y) {
Dia t = x.dis > y.dis ? x : y;
int res = Get(x.a, y.a);
if (res > t.dis) t = {x.a, y.a, res};
res = Get(x.a, y.b);
if (res > t.dis) t = {x.a, y.b, res};
res = Get(x.b, y.a);
if (res > t.dis) t = {x.b, y.a, res};
res = Get(x.b, y.b);
if (res > t.dis) t = {x.b, y.b, res};
return t;
}
inline void merge(int x, int y) {
int fx = UNQ::Find(x);
int fy = UNQ::Find(y);
UNQ::Merge(x, y);
d[fy] = Mrg(d[fx], d[fy]);
}
inline void Init() {
dfs(1);
for (int i = 1; i <= n; ++ i)
d[i] = {i, i, 0};
for (int i = 1; i < n; ++ i)
if (!cut[i])
merge(a[i], b[i]);
}
inline void Solve() {
for (int i = m; i; -- i)
if (q[i].op == 1) {
merge(a[q[i].x], b[q[i].x]);
} else {
int res = 0, fx = UNQ::Find(q[i].x);
res = max(Get(d[fx].a, q[i].x), Get(d[fx].b, q[i].x));
ans[i] = res;
}
for (int i = 1; i <= m; ++ i)
if (q[i].op == 2)
printf ("%d\n", ans[i]);
}
int main()
{
scanf ("%d%d", &n, &m);
for (int i = 1; i < n; ++ i) {
scanf ("%d%d", a + i, b + i);
add(a[i], b[i]), add(b[i], a[i]);
}
for (int i = 1; i <= m; ++ i) {
scanf ("%d%d", &q[i].op, &q[i].x);
if (q[i].op == 1) cut[q[i].x] = 1;
}
UNQ::Init(n); Init();
Solve();
return 0;
}