题解 P2542 【[AHOI2005]航线规划】

一只蒟蒻介绍一种可能不太难想的解法。 ~~（那些大佬好像都写了什么缩点双还是什么的，蒟蒻瑟瑟发抖啊$QAQ$）~~ 不难想到要反向处理。 然后题目就变成了：先给一些边，然后不断加边，求$x-y$关键边数量。 因为只有加边操作，所以实际上只有关键边变非关键边，而不存在非关键边变成关键边。 不难发现，一条边如果为关键边，那么其联通了两个联通块，且没有其他边联通这两个联通块，所以对于一条关键边，从其联通的两个联通块中任意两个点到对方点的路径中其都为关键边，简单来讲，就是 **一条关键边对于任意两个过其的点都是关键边** 故我对每个边维护一下其是否为关键边，如果是其边权为$1$，否则其边权为$0$ 由于前面加粗的字体所描述的优秀性质，所以我们询问$x-y$的路径上有多少关键路径，就是询问$x-y$的路径上边权和 有加边操作，所以考虑使用$LCT$，然后要把边拆为点。 现在考虑加边怎么做： 如果一条边连接了两个现在未联通的点，那么直接加边，且加入的这条边显然是一条关键边，假设当前边的编号为$Idnex$，那么$w[Idnex]=1$。 如果一条连接了两个已经联通的点呢？ 看图理解$QWQ$ 现在的图是这个样子的：  我们加入一条这样的边，那么这条边连接了两个已经联通的点，其显然是一个非关键边。  图中的红边是一条非关键边。 然后考虑其对答案的影响。 其会导致这些边变成非关键边：  （图中绿边） 那么我们如何把这些边改成非关键边？就是要将这些边的点权改为0 不难发现一条这样的红边对答案产生的影响就是：$x-y$的路径中的所有边。 这些边的边权都要被改为$0$ 所以如果一条边连接的两个点在同一联通块内，就把这一条链拉出来，把边权全部覆盖为$0$，就操作如下： 先$slipt(x,y)$，然后给打上一个覆盖标记。 细节看代码$QWQ$ ```cpp #include<bits/stdc++.h> using namespace std; int read() { char cc = getchar(); int cn = 0, flus = 1; while(cc < '0' || cc > '9') { if( cc == '-' ) flus = -flus; cc = getchar(); } while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar(); return cn * flus; } #define ls(x) t[x].son[0] #define rs(x) t[x].son[1] #define rep( i, s, t ) for( register int i = s; i <= t; ++ i ) #define drep( i, t, s ) for( register int i = t; i >= s; -- i ) const int N = 200000 + 5; struct LCT { int son[2], val, fa, cover; bool mark; }t[N]; struct E{ int from, to, c; }e[N]; map< int, int > mc1; int n, m, Opt[N], From[N], To[N], tot, w[N], Idnum, ans[N], Id[N]; void pushup( int x ) { t[x].val = t[ls(x)].val + t[rs(x)].val + w[x]; } void push( int x ) { //cover表示覆盖标记，如果有覆盖标记，则此点的w值应改为0，且整棵子树都要被改为0 // 所以还要修改t[x].val = 0 w[x] = 0, t[x].cover = 1, t[x].val = 0; } void pushmark( int x ) { if( t[x].cover ) // 下传标记 t[x].cover = 0, push( ls(x) ), push( rs(x) ), t[x].val = 0; if( t[x].mark ) t[x].mark = 0, t[ls(x)].mark ^= 1, t[rs(x)].mark ^= 1, swap( ls(x), rs(x) ); } bool isroot( int x ) { return ( rs(t[x].fa) != x ) && ( ls(t[x].fa) != x ); } void rotate( int x ) { int f = t[x].fa, ff = t[f].fa, qwq = ( rs(f) == x ); t[x].fa = ff; if( !isroot(f) ) t[ff].son[rs(ff) == f] = x; t[t[x].son[qwq ^ 1]].fa = f, t[f].son[qwq] = t[x].son[qwq ^ 1]; t[x].son[qwq ^ 1] = f, t[f].fa = x; pushup(f), pushup(x); } int st[N]; void Splay( int x ) { int top = 0, now = x; st[++top] = now; while( !isroot(now) ) st[++top] = ( now = t[now].fa ); while( top ) pushmark( st[top--] ); while( !isroot(x) ) { int f = t[x].fa, ff = t[f].fa; if( !isroot(f) ) ( ( rs(ff) == f ) ^ ( rs(f) == x ) ) ? rotate(x) : rotate(f); rotate(x); } } void access( int x ) { for( int y = 0; x; y = x, x = t[y].fa ) Splay(x), t[x].son[1] = y, pushup(x); } void makeroot( int x ) { access( x ), Splay( x ), t[x].mark ^= 1, pushmark( x ); } int findroot( int x ) { access( x ), Splay( x ), pushmark( x ); while( ls(x) ) pushmark( x = ls(x) ); return x; } void split( int x, int y ) { makeroot(x), access(y), Splay(y); } void link( int x, int y ) { makeroot( x ); if( findroot(y) != x ) t[x].fa = y; } bool check( int x, int y ) { makeroot( x ); return findroot(y) == x; } void input() { n = read(), m = read(); rep( i, 1, m ) { e[i].from = read(), e[i].to = read(); if( e[i].from > e[i].to ) swap( e[i].from, e[i].to ); //swap, 方便统计 mc1[e[i].from * ( n + 1 ) + e[i].to] = i, w[i + n] = 1; //拆边，每条边的编号都是i+n， //同时在map内记录，方便查初始有那些边存在 } while( 1 ) { Opt[++ tot] = read(); //表示是那种操作 if( Opt[tot] == -1 ) break; From[tot] = read(), To[tot] = read(); if( Opt[tot] == 0 ) { if( From[tot] > To[tot] ) swap( From[tot], To[tot] ); Id[tot] = mc1[From[tot] * ( n + 1 ) + To[tot]]; e[Id[tot]].c = 1; //标记这条边被用过了 } } } signed main() { input(); //读入函数 rep( i, 1, m ) { if( !e[i].c ) { //若这条边没有被用过 int u = e[i].from, v = e[i].to; if( check( u, v ) ) split( u, v ), push(v); //如果u，v 在一个联通块内，则拉出u到v的链，然后打上标记 else link( e[i].from, i + n ), link( i + n, e[i].to ); //否则直接连边 } } drep( i, tot - 1, 1 ) { if( Opt[i] == 0 ) { //如果是0，就是连边操作，与前面类似 int u = From[i], v = To[i]; if( check( u, v ) ) split( From[i], To[i] ), push(To[i]); else link( From[i], Id[i] + n ), link( Id[i] + n, To[i] ); } if( Opt[i] == 1 ) //否则就是询问，直接split然后统计答案 split( From[i], To[i] ), ans[++Idnum] = t[To[i]].val; } drep( i, Idnum, 1 ) printf("%d\n", ans[i]); return 0; } ```