东南融通网站建设,安徽工程建设信息网站6,微信多账号管理系统,深圳市建设银行网站Link Cut Tree 学习笔记 说在前边 最近补 CF 碰见一道 LCT #xff0c;就打算学习一下这个东西。。。顺便复习一下 splay。 具体算法及实现 参考了FlashHu#xff0c; Candy? P3690 【模板】Link Cut Tree #xff08;动态树#xff09; 题目#xff1a;给定n个点以及每个… Link Cut Tree 学习笔记 说在前边 最近补 CF 碰见一道 LCT 就打算学习一下这个东西。。。顺便复习一下 splay。 具体算法及实现 参考了FlashHu Candy? P3690 【模板】Link Cut Tree 动态树 题目给定n个点以及每个点的权值要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。 0后接两个整数(xy)代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。 1后接两个整数(xy)代表连接x到y若x到y已经联通则无需连接。 2后接两个整数(xy)代表删除边(xy)不保证边(xy)存在。 3后接两个整数(xy)代表将点x上的权值变成y。 做法模板 Code #include cstdio
#include algorithm
#include cstring
#include cstdlib
#include cctype
typedef long long ll;
const int N 300010;
const int inf 0x3f3f3f3f;
templateclass T inline void read(T x) {x 0; char c getchar(); T f 1;while(!isdigit(c)) {if(c -) f -1; c getchar();}while(isdigit(c)) {x x * 10 c - 0; c getchar();}x * f;
}
using namespace std;
class LCT {
private :struct Node {int ch[2], fa, rev, sum, w;} T[N];int st[N];#define lc T[p].ch[0]#define rc T[p].ch[1]#define pa T[p].fainline int LR(int p) { return T[pa].ch[1] p; }inline int isR(int p) { return T[pa].ch[0] ! p T[pa].ch[1] ! p; }inline void PushUp(int p) { T[p].sum T[lc].sum ^ T[rc].sum ^ T[p].w; }inline void Pushr(int p) { T[p].rev ^ 1; swap(lc, rc); }inline void PushDown(int p) {if(T[p].rev) {if(lc) Pushr(lc);if(rc) Pushr(rc);T[p].rev 0;}}inline void rotate(int p) {int fT[p].fa, gT[f].fa, cLR(p);if(!isR(f)) T[g].ch[LR(f)]p; T[p].fag;T[f].ch[c] T[p].ch[c^1]; T[T[f].ch[c]].faf;T[p].ch[c^1] f; T[f].fap;PushUp(f); PushUp(p);}inline void splay(int p) {int yp,z0; st[z]y;while(!isR(y)) st[z]yT[y].fa;while(z) PushDown(st[z--]);while(!isR(p)) {yT[p].fa;zT[y].fa;if(!isR(y)) rotate((T[y].ch[0]p)^(T[z].ch[0]y)?p:y);rotate(p);}PushUp(p);}inline void access(int p) {for(int y 0; p; p T[y p].fa)splay(p), rc y, PushUp(p);}inline void makeR(int p) {access(p); splay(p); Pushr(p);}int findR(int p) {access(p); splay(p);while(lc) PushDown(p), p lc;splay(p);return p;}
public :inline void split(int x, int y) {makeR(x); access(y); splay(y);}inline void Link(int x, int y) {makeR(x);if(findR(y)!x)T[x].fay;}inline void Cut(int x, int y) {makeR(x);if(findR(y) x T[y].fa x !T[y].ch[0]) {T[y].fa T[x].ch[1] 0; PushUp(x);}}inline int getSum(int p) { return T[p].sum; }inline void setW(int p, int v) { splay(p);T[p].w v;PushUp(p); }
} tree;
int n, q, opt, u, v;
int main() {read(n), read(q);for(int i 1; i n; i) read(v), tree.setW(i, v);while(q--) {read(opt), read(u), read(v);if(opt 0) tree.split(u, v), printf(%d\n,tree.getSum(v));else if(opt 1) tree.Link(u, v);else if(opt 2) tree.Cut(u, v);else if(opt 3) tree.setW(u, v);}
} CodeForces 1137F 题意给定一棵n点树。设第i个点当前编号为\(p_i\)。已知一种游戏每次删除叶子节点中编号最小的那个节点而节点\(v\)在一次游戏中被删除的时间为\(Ti(v)\)。有\(m\)组询问三种操作1. \(up ~v\)将 \(v\) 点标号改为\(1 max(p_1,p_2,...,p_n)\) 2. \(when ~v\)询问 \(Ti(v)\) 3.\(compare ~u~v\), 比较\(Ti(u)\), \(Ti(v)\)。 做法首先操作3可以转化为操作2。现在假设我们已经知道当前这棵树每个节点的\(Ti\)那么当进行\(up\)操作时这棵树的\(Ti\)会怎么变化测试几组数据可以知道每次只有原本的最大值与新的最大值路径上的\(Ti\)会发生重编号而这条链之外的节点的\(Ti\)相对大小没有改变。 为了操作方便我们用编号最大的点作为当前的根节点考虑如何询问。我们定义\(mxp(v)\)为\(v\)子树中最大的点的编号对于一个节点\(v\)和一个节点\(u\)如果\(mxp(v) mxp(u)\)\(v\)一定先于\(u\)删除因为在删除\(mxp(u)\)之前一定已经删除了\(mxp(v)\)而删除了\(mxp(v)\)之后一定会继续删除直到删除\(v\)。对于一个点\(u\)所有满足\(mxp(v) mxp(u)\) 的\(v\) 一定先于他删除。如果\(mxp(v) mxp(u)\) 出现这种情况当且仅当\(u\)和\(v\)在一条指向根的路径上那么由于根节点的编号最大我们一定会先删除深度比较深的点。所以形式化的答案是\[ \sum_v [mxp(v) mxp(u)] \sum_v [mxp(v)mxp(u)][dep[v] dep[u]] \\ \sum_v [mxp(v) \leq mxp(u)] - \sum_v [mxp(v)mxp(u)][dep[v] dep[u]] \] 现在整理一下我们要维护什么每个点子树中的最大编号深度信息编号小于\(v\)的点的数目编号为\(v\)的点中\(dep\)小于\(d\)的数目要支持把编号最大点提到根的位置。 涉及到提根这个操作所以想到使用\(LCT\)解决。每个辅助树的节点中除了常规的部分维护\(mxp\)和子树的大小\(sz\)而同时因为\(LCT\)的性质其中每个\(splay\)中都是按照深度排序。再利用一个树状数组维护编号小于\(v\)的点的数目。 初始化部分我们\(dfs\)这棵树求出每个点的父亲同时我们将所有的点按照\(mxp\)连成一条条实链顺便计算\(sz\)以及在树状数组中更新。 对于询问操作\(when ~v\)答案就是小于等于\(mxp(v)\)的\(mxp(u)\)的数量减去深度小于\(v\)的\(mxp\)相同的点的数量。对于第一部分直接在树状数组中查询第二部分利用\(splay\)的按深度排序的性质我们\(splay(v)\)将\(v\)旋到根上此时它的左子树的\(sz\)就是我们要的。 对于修改操作\(up ~v\)我们令原先最大的点为\(u\), \(access(v)\) 同时将所有v到u路径上的点的编号改为\(mxp(u)\)把\(v\)旋到根再翻转这条链此时\(v\)已经是整颗树的根了但是此时的\(v\)的编号还没有修改我们把\(u\)和它的右儿子断开重新给他打上新的标记即可。 这个过程中要注意打上标记后及时\(pushdown\)子节点修改后及时\(pushup\)。 ps: 这题从复习\(splay\)学习\(LCT\)到看懂题解花了3天时间。参考了很多ac代码。。。 Code #include bits/stdc.h
#define pb push_back
typedef long long ll;
const int N 200010;
templateclass T inline void read(T x) {x 0; char c getchar(); T f 1;while(!isdigit(c)) {if(c -) f -1; c getchar();}while(isdigit(c)) {x x * 10 c - 0; c getchar();}x * f;
}
using namespace std;
class BIT {int n, a[N 1];
public :void init(int _) {n _;}void add(int p, int val) {for(int i p; i n; i (i(-i))) a[i] val;}int ask(int p) { int ans 0;for(int i p; i; i - (i(-i))) ans a[i];return ans;}
} B;
struct Node {int ch[2], fa, rev, sz, w, tag;
} T[N];
#define lc T[p].ch[0]
#define rc T[p].ch[1]
#define pa T[p].fa
inline int LR(int p) { return T[pa].ch[1] p; }
inline int isR(int p) { return T[pa].ch[0] ! p T[pa].ch[1] ! p; }
inline void PushUp(int p) { T[p].sz T[lc].sz T[rc].sz 1; }
inline void Pushr(int p) { T[p].rev ^ 1; swap(lc, rc); }
inline void PushDown(int p) {if(T[p].rev) {if(lc) Pushr(lc);if(rc) Pushr(rc);T[p].rev 0;}if(T[p].tag) {T[lc].tag T[lc].w T[p].tag;T[rc].tag T[rc].w T[p].tag;T[p].tag 0;}
}
inline void rotate(int p) {int fT[p].fa, gT[f].fa, cLR(p);if(!isR(f)) T[g].ch[LR(f)]p; T[p].fag;T[f].ch[c] T[p].ch[c^1]; T[T[f].ch[c]].faf;T[p].ch[c^1] f; T[f].fap;PushUp(f); PushUp(p);
}
inline void splay(int p) {static int st[N];int yp,z0; st[z]y;while(!isR(y)) st[z]yT[y].fa;while(z) PushDown(st[z--]);while(!isR(p)) {yT[p].fa;zT[y].fa;if(!isR(y)) rotate((T[y].ch[0]p)^(T[z].ch[0]y)?p:y);rotate(p);}
}
inline void access(int p, int ti) {for(int y 0; p; p T[y p].fa) {splay(p); // splay 到顶T[p].ch[1] 0; // 断掉比他深的点PushUp(p); // **// updateB.add(T[p].w, -T[p].sz);T[p].tag T[p].w ti;B.add(T[p].w, T[p].sz);T[p].ch[1] y;// 右儿子接到上一层splay的根上PushUp(p); // **}
}int n, q, u, v;
char opt[11];
vectorint G[N];
void dfs(int u) {T[u].w u;for(int v: G[u]) if(v ! T[u].fa) {T[v].fa u; dfs(v);T[u].w max(T[u].w, T[v].w);}for(int v: G[u]) if(v ! T[u].fa T[u].w T[v].w) {T[u].ch[1] v;T[u].sz T[v].sz 1;}B.add(T[u].w, 1);
}
int qry(int p) {splay(p); PushDown(p);return B.ask(T[p].w) - T[lc].sz;
}int main() {
#ifdef RRRR_wysfreopen(in.txt,r,stdin);
#endifread(n), read(q);B.init(nq2);for(int i 2; i n; i)read(u), read(v), G[u].pb(v), G[v].pb(u);for(int i 1; i n; i) T[i].sz 1;dfs(n); int TT n;while(q--) {scanf( %s,opt);if(opt[0] u) {read(v);// MakeRootaccess(v, TT); splay(v);T[v].rev ^ 1; swap(T[v].ch[0], T[v].ch[1]);PushDown(v);// updateB.add(T[v].w, -1); // ***T[v].ch[1] 0; // 断右儿子T[v].w T[v].tag TT; // 重新标号T[v].sz 1; // 计算szB.add(T[v].w, 1);}else if(opt[0] w) {read(v);printf(%d\n, qry(v));}else {read(u), read(v);printf(%d\n, (qry(u) qry(v) ? u : v) );}}
} 转载于:https://www.cnblogs.com/RRRR-wys/p/10527816.html
