题解 P4172 【[WC2006]水管局长】

人生第一道深蓝题~~当然要写一下题解辣！ ## 题意： 给一个n个点m条边的图，支持以下操作： 1. 询问x到y所有路径中，路径上最大边权的最小值 2. 删去一条边 ## 做法： link-cut-tree通常用来解决树上一些动态加边、删边的问题。 如果不会lct可以先自己去学习一下，打几道模板~~（bzoj上全是~~。这里讲一下大致内容。（不过建议还是自己去好好理解消化一下，本人初学lct的时候也是理解了好久的qwq > 称一个点被访问过, 如果刚刚执行了对这个点的 ACCESS 操作. > 如果结点 v 的子树中, 最后被访问的结点在子树 w 中, 这里 w 是 v 的儿子, 那么就称 w 是 v 的 Preferred Child. 如果最后被访问过的结点就是 v 本身, 那么它没有 Preferred Child. 每个点到它的 Preferred Child 的边称作 Preferred Edge. 由 Preferred Edge 连接成的不可再延伸的路径称为 Preferred Path. > 这样, 整棵树就被划分成了若干条 Preferred Path. 对每条 Preferred Path, 用这条路上的点的深度作为关键字, 用一棵平衡树来维护它(在这棵平衡树中, 每个点的左子树中的点, 都在 Preferred Path 中这个点的上方; 右子树中的点, 都在 Preferred Path 中这个点的下方). 需要注意的是, 这种平衡树必须支持分离与合并. 这里, 我们选择 Splay Tree 作为这个平衡树的数据结构. 我们把这棵平衡树称为一棵 Auxiliary Tree. > 知道了树 T 分解成的这若干条 Preferred Path, 我们只需要再知道这些路径之间的连接关系, 就可以表示出这棵树 T . 用 Path Parent 来记录每棵 Auxiliary Tree 对应的 Preferred Path 中的最高点的父亲结点,如果这个 Preferred Path 的最高点就是根结点, 那么令这棵 Auxiliary Tree 的 Path Parent 为 null. > Link-Cut Trees 就是将要维护的森林中的每棵树 T 表示为若干个 Auxiliary Tree, 并通过 Path Parent 将这些 Auxiliary Tree 连接起来的数据结构. lct的主要操作基于ACCESS操作，来看一下ACCESS操作的流程： > ACCESS 操作是 Link-Cut Trees 的所有操作的基础. 假设调用了过程 ACCESS(v), 那么从点 v 到根结点的路径就成为一条新的 Preferred Path. 如果路径上经过的某个结点 u 并不是它的父亲 parent(u) 的 Preferred Child, 那么由于 parent(u) 的 Preferred Child 会变为 u , 原本包含 parent(u) 的 Preferred Path 将不再包含结点 parent(u) 及其之上的部分. > 首先, 由于访问了点 v, 那么它的 Preferred Child 应当消失. 先将点 v 旋转到它所属的 Auxiliary Tree 的根, 如果 v 在 v 所属的 Auxiliary Tree 中有右儿子(也就是 v 原来的 Preferred Child), 那么应该将 v 在 v 所属的 Auxiliary Tree 中的右子树(对应着它的原来的 Preferred Child 之下的 Preferred Path)从 v 所属的 Auxiliary Tree 中分离, 并设置这个新的 Auxiliary Tree 的 Path Parent 为 v.然后, 如果点 v 所属的 Preferred Path 并不包含根结点, 设它的 Path Parent 为 u, 那么需要将 u 旋转到 u 所属的 Auxiliary Tree 的根, 并用点 v 所属的 Auxiliary Tree 替换到点 u 所属的 Auxiliary Tree 中点 u 的右子树, 再将原来点 u 所属的 Auxiliary Tree 中点 u 的右子树的 Path Parent 设置为 u. 如此操作,直到到达包含根结点的 Preferred Path. ——以上所有引用部分来源于`yang zhe`的《QTREE 解法的一些研究》论文。 于是各种连边、删边、换根操作就可以执行了，具体见代码。 ------ 然后我们来考虑这道题。 我们发现删边特别难处理，那么怎样转化一下呢？倒着处理所有询问，于是删边变成了加边。然后查询所有路径上最大值的最小值，不难发现就是要维护这个图的最小生成树，然后就可以直接查询树路径上的最大值了，也可以用lct做到。那么问题转化为了**动态维护最小生成树**。 我们此时已经将询问倒过来处理了，那么假设我们已经维护好了一棵mst，每加一条边u-v，肯定会形成一个**环**。因为是最小生成树，所以我们肯定要在环上去掉一条最大的边。于是处理加边操作流程如下： > 1. 查询u-v链上最大边权mx > 2. 比较新加的边权w和mx的大小关系，如果 $w>mx$ ，则不做任何操作；否则删去边权为mx的边(cut)，加上u-v这条边(link)。 那么查询就直接查链上最大值即可。 ------ 至此，此题大致流程已经结束。 不过还有一些小问题： 1. 在保存mx的时候需要存的是边的编号，因为到时加边的时候需要用到。 2. 你发现lct似乎只能处理链上最大点权而无法保存边权。怎么办呢？我们可以考虑 **把边看成点** ，加一条边u-v，编号为id，则 `link(u, id); link(v, id);` ；删边同理。 3. 在处理询问的时候需要找到某条边的编号，可以开一个map记录边的编号。 ## 代码： 好辣好辣泥萌是不是已经急着想看代码辣qwqwq 那接下来就是看~~膜~~代码时间~ ```cpp #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<iostream> #include<cmath> #include<cstdlib> #include<cctype> #include<map> #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; inline ll read() { char ch = getchar(); ll x = 0; int op = 1; for(; !isdigit(ch); ch = getchar()) if(ch == '-') op = -1; for(; isdigit(ch); ch = getchar()) x = x*10+ch-'0'; return x*op; } inline void write(ll a) { if(a < 0) putchar('-'), a = -a; if(a >= 10) write(a/10); putchar('0'+a%10); } const int N = 100010, M = 1000010; int n, m, que; int ans[N]; bool vis[M]; map<pii, int> id; struct edge { int x, y, z; } e[M]; struct questions { int opt, x, y, flag; } q[N]; const bool cmp(const edge &a, const edge &b) { return a.z < b.z; } const int S = N+M; int rev[S], fa[S], c[S][2], mx[S], val[S]; inline bool isroot(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; } inline void pushup(int x) { mx[x] = val[x]; if(e[mx[c[x][0]]].z > e[mx[x]].z) mx[x] = mx[c[x][0]]; if(e[mx[c[x][1]]].z > e[mx[x]].z) mx[x] = mx[c[x][1]]; } inline void rot(int x) { if(isroot(x)) return; int y = fa[x], z = fa[y], f = c[y][1] == x; c[y][f] = c[x][f^1]; if(c[x][f^1]) fa[c[x][f^1]] = y; fa[x] = z; if(!isroot(y)) c[z][c[z][1] == y] = x; fa[y] = x; c[x][f^1] = y; pushup(y); pushup(x); } inline void pushdown(int x) { if(!rev[x]) return; rev[c[x][0]] ^= 1; rev[c[x][1]] ^= 1; swap(c[x][0], c[x][1]); rev[x] = 0; } int st[N], top; inline void pushtag(int x) { top = 0; while(x) { st[++ top] = x; x = fa[x]; } while(top) pushdown(st[top --]); } inline void splay(int x) { pushtag(x); while(!isroot(x)) { int y = fa[x], z = fa[y]; if(!isroot(y)) rot(((c[z][0] == y) == (c[y][0] == x))?y:x); rot(x); } } inline void access(int x) { int t = 0; while(x) { splay(x); c[x][1] = t; pushup(x); t = x; x = fa[x]; } } inline void rever(int x) { access(x); splay(x); rev[x] ^= 1; } inline void link(int x, int y) { rever(x); fa[x] = y; } inline void split(int x, int y) { rever(x); access(y); splay(y); } inline void cut(int x, int y) { split(x, y); fa[x] = c[y][0] = 0; } inline int find(int x) { access(x); splay(x); pushdown(x); while(c[x][0]) { x = c[x][0]; pushdown(x); } return x; } inline void init(int x, int y) { fa[x] = c[x][0] = c[x][1] = rev[x] = 0; mx[x] = val[x] = y; } int main() { /*freopen("tube.in", "r", stdin); freopen("tube.out", "w", stdout);*/ n = read(), m = read(), que = read(); for(int i = 1; i <= m; i ++) { e[i].x = read(); e[i].y = read(); e[i].z = read(); if(e[i].x > e[i].y) swap(e[i].x, e[i].y); } sort(e+1, e+1+m, cmp); for(int i = 1; i <= m; i ++) id[mp(e[i].x, e[i].y)] = i; for(int i = 1; i <= que; i ++) { q[i].opt = read(); q[i].x = read(); q[i].y = read(); if(q[i].x > q[i].y) swap(q[i].x, q[i].y); if(q[i].opt == 2) { int d = id[mp(q[i].x, q[i].y)]; q[i].flag = d;//flag表示q[i]这条边在e中的编号 vis[d] = 1; } } int all = n+m, sum = 0; e[0].z = 0; for(int i = 1; i <= all; i ++) init(i, i<=n?0:(i-n)); for(int i = 1, x, y; i <= m; i ++) if(!vis[i]) { if(sum == n-1) break; x = e[i].x; y = e[i].y; if(find(x) == find(y)) continue; link(x, i+n); link(y, i+n); sum ++; } for(int i = que, x, y; i >= 1; i --) { x = q[i].x; y = q[i].y; if(q[i].opt == 1) { split(x, y); ans[i] = e[mx[y]].z; } else { split(x, y); int d = q[i].flag, t = mx[y]; if(e[d].z < e[mx[y]].z) { cut(e[t].x, t+n); cut(e[t].y, t+n); link(x, d+n); link(y, d+n); } } } for(int i = 1; i <= que; i ++) if(q[i].opt == 1) write(ans[i]), puts(""); return 0; } ``` **后话：** emmm我写了这么多也是挺累的，泥萌觉得好的话一定要兹瓷一下嗷！赞一下很快的嗷~qwqwqwq 也鼓励我一下以后能继续写好的题解！ 有什么缺点也尽管提出来~欢迎的嗷~