无锡正规网站seo公司,有一个做名片的网站,爱客crm系统,网页设计页面图片原题链接
题意
动态求 LCA 板子题。
维护一个森林#xff0c;支持加边、删边和求 LCA 操作。
思路
不难想到 LCT。
现在问题就是如何在 LCT 上求两个点 u , v u,v u,v 的 LCA。
先进行 access ( u ) \operatorname{access}(u) access(u)#xff0c;此时 u u u 到…原题链接
题意
动态求 LCA 板子题。
维护一个森林支持加边、删边和求 LCA 操作。
思路
不难想到 LCT。
现在问题就是如何在 LCT 上求两个点 u , v u,v u,v 的 LCA。
先进行 access ( u ) \operatorname{access}(u) access(u)此时 u u u 到根的路径已经变成一个实链。 lca ( u , v ) \operatorname{lca}(u,v) lca(u,v) 去往 u u u 的路径的第一条边是实边则去往 v v v 的路径的第一条边是虚边。
再进行 access ( v ) \operatorname{access}(v) access(v)由于 lca ( u , v ) \operatorname{lca}(u,v) lca(u,v) 到根的路径上全是实边那么 access \operatorname{access} access 最后改变的虚边的父亲就是 lca ( u , v ) \operatorname{lca}(u,v) lca(u,v)。
注意求 LCA 需要考虑树的父子关系所以在 cut 时不能使用 makeroot 操作而 link 无所谓。 代码
#include iostreamusing namespace std;const int N 100010;int n, m;
struct Splay_Node
{int s[2], p, v;
}tr[N];inline bool is_root(int x)
{int p tr[x].p;if (tr[p].s[0] ! x tr[p].s[1] ! x) return true;return false;
}inline void rotate(int x)
{int y tr[x].p, z tr[y].p;int k tr[y].s[1] x;if (!is_root(y)) tr[z].s[tr[z].s[1] y] x;tr[x].p z;tr[y].s[k] tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p y;tr[x].s[k ^ 1] y, tr[y].p x;
}inline void splay(int x)
{while (!is_root(x)){int y tr[x].p, z tr[y].p;if (!is_root(y))if ((tr[y].s[1] x) ^ (tr[z].s[1] y)) rotate(x);else rotate(y);rotate(x);}
}inline int access(int x)
{int z x, y;for (y 0; x; y x, x tr[x].p)splay(x), tr[x].s[1] y;splay(z);return y; // 这里返回的是最后一次虚实链变换时虚边父亲节点的编号。
}inline int find_root(int x)
{access(x);while (tr[x].s[0]) x tr[x].s[0];splay(x);return x;
}inline void link(int x, int y)
{if (find_root(y) ! find_root(x)) tr[x].p y;
}inline void cut(int x) // 一定不能 makeroot
{access(x);tr[x].s[0] tr[tr[x].s[0]].p 0;
}inline int lca(int x, int y)
{access(x);return access(y);
}int main()
{char op[5]; int x, y;scanf(%d%d, n, m);while (m -- ){scanf(%s%d%d, op, x, y);if (op[1] i) link(x, y);else if (op[1] u) cut(x);else printf(%d\n, lca(x, y));}return 0;
}
