刚刚做了这个版块的题，所以趁热打铁..(有些铁已经凉了）

基本定义

LCA，就是在一棵树上找两个节点最近的公共祖先(可以理解在哪个点的时候最先相交）。

针对这类问题，我们可以用倍增的方法实现

由于以前博客写过代码，所以就不写了：自己来复习

现在开始讲例题：

习题题解：

1.Meet 紧急集合

思路

这道题其实就是三个点的LCA，但是不同的是，由于有三个点，哪一个作为集合点呢？

其实可知，集合点一定在a-b,a-c,b-c这三条路径中重合的某一个点上肯定最小。

那么怎么确定是哪一个点呢？

我们可以分类讨论，三种情况：

（一）

没有说的，选点1

（二）

这种情况是选到1吗？

其实不是，是选到a才最短

（三）

那这种情况的话，a或c都可以

经验证，我们可以得出选择最深的LCA是最好的

所以就开始码代码了

代码

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> using namespace std; const int MAXN = 5e5 + 3; int n , m; int f[MAXN][30]; int sz[MAXN] , fa[MAXN]; vector< int > G[MAXN]; void dfs( int x , int fa1 ){ for( int i = 0 ; i < G[x].size() ; i ++ ){ int v = G[x][i]; if( fa1 == v ) continue; sz[v] = sz[x] + 1; fa[v] = x; f[v][0] = x; dfs( v , x ); } } void pre( ){ sz[1] = 1; dfs( 1 , 1 ); for( int j = 1 ; j <= 20 ; j ++ ) for( int i = 1 ; i <= n ; i ++ ) f[i][j] = f[f[i][j-1]][j-1]; } void jump( int &x , int mu ){ for( int i = 20 ; i >= 0 ; i -- ) if( sz[f[x][i]] >= mu ) x = f[x][i]; } int LCA( int x , int y ){ if( sz[x] > sz[y] ) jump( x , sz[y] ); else if( sz[x] < sz[y] ) jump( y , sz[x] ); if( x != y ){ for( int i = 20 ; i >= 0 ;i -- ) if( f[x][i] != f[y][i] ) x = f[x][i] , y = f[y][i]; x = f[x][0]; } return x; } int main() { scanf( "%d%d" , &n , &m ); for( int i = 1 ; i < n ; i ++ ){ int x , y; scanf( "%d%d" , &x , &y ); G[x].push_back( y ); G[y].push_back( x ); } pre(); for( int i = 1 ; i <= m ; i ++ ){ int x , y , z; scanf( "%d%d%d" , &x , &y , &z ); int ans1 = LCA( x , y ); int ans2 = LCA( y , z ); int ans3 = LCA( x , z ); int p = ans1; if( sz[ans1] < sz[ans2] ) p = ans2; if( sz[p] < sz[ans3] ) p = ans3; printf( "%d " , p ); int sum = ( sz[x] - sz[ans1] + sz[y] - sz[ans1] ) + ( sz[y] - sz[ans2] + sz[z] - sz[ans2] ) + ( sz[x] - sz[ans3] + sz[z] - sz[ans3] ); printf( "%d" , sum / 2 ); if( i != m ) printf( "\n" ); } return 0; }

2.跳跳棋

思路

这也是一道神题....

我们首先考虑暴力搜索思路，那么其实可供转换的只有三种状态

1.中间的棋子往两边跳（两种）

2.边上的棋子距离中点更近的可以往中间跳

然后，这就是一颗二叉树了

1是通向儿子，2是通向父亲

那么大概思路就有了：

我们把三个棋子的位置看做一种状态

我们用类似LCA的做法来做。

首先，我们去判断是否这两种状态的根相同，就是两边的向中间的跳

这样可以直接判断输出NO

但是如果一步步跳太慢了，我们可以几步几步地跳：

 

画得真得丑，能看懂就行

那么第一步就实现了，现在我们已经求出了深度（步数），现在我们要把两个节点移到统一高度

一样的做法

接着，我们就开始用LCA的方法做就行了。

代码

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> using namespace std; #define ll long long ll a , b , c; ll step1 = 0 , step2 = 0; ll ma , mb , mc; ll ans; ll ma1 , mb1 , mc1 , a1 , b1 , c1; ll s[5] , l[5]; void js( ll &x , ll &y , ll &z , ll &step ){ ll d1 = y - x , d2 = z - y; while( d1 != d2 ){ if( d1 < d2 ){ ll s = d2 / d1 , m = d2 % d1; if( !m ){ step += s - 1; x += d1 * (s - 1), y += d1 * (s - 1); return ; } step += s , x += d1 * s , y += d1 * s , d2 = m; } else{ ll s = d1 / d2 , m = d1 % d2; if( !m ){ step += s - 1; y -= d2 * (s - 1), z -= d2 * (s - 1); return ; } step += s , y -= d2 * s , z -= d2 * s , d1 = m; } } } void tz( ll &x , ll &y , ll &z , ll step ){ ll d1 = y - x , d2 = z - y; while( step > 0 ){ if( d1 < d2 ){ ll s = d2 / d1 , m = d2 % d1; if( !m ){ s --; if( step < s ) s = step ; x += d1 * s , y += d1 * s; step -= s; return ; } if( step < s ) s = step; x += d1 * s , y += d1 * s , d2 = m; step -= s; } else{ ll s = d1 / d2 , m = d1 % d2; if( !m ){ s --; if( step < s ) s = step ; z -= d2 * s , y -= d2 * s; step -= s; return ; } if( step < s ) s = step; z -= d2 * s , y -= d2 * s , d1 = m; step -= s; } } } int main(){ for( int i = 1 ; i <= 3 ; i ++ ) scanf( "%lld" , &s[i] ); sort( s + 1 , s + 3 + 1 ); a = s[1] , b = s[2] , c = s[3]; for( int i = 1 ; i <= 3 ; i ++ ) scanf( "%lld" , &l[i] ); sort( l + 1 , l + 3 + 1 ); ma = l[1] , mb = l[2] , mc = l[3]; a1 = a , b1 = b , c1 = c; js( a1 , b1 , c1 , step1 ); ma1 = ma , mb1 = mb , mc1 = mc; js( ma1 , mb1 , mc1 , step2 ); l[1] = ma1 , l[2] = mb1 , l[3] = mc1; sort( l + 1 , l + 3 + 1 ); s[1] = a1 , s[2] = b1 , s[3] = c1; sort( s + 1 , s + 3 + 1 ); for( int i = 1 ; i <= 3 ; i ++ ){ if( s[i] != l[i] ){ printf( "NO\n" ); return 0; } } printf( "YES\n" ); if( step1 < step2 ){ tz( ma , mb , mc , step2 - step1 ); ans = step2 - step1; } else if( step1 > step2 ){ tz( a , b , c , step1 - step2 ); ans = step1 - step2; } ll l1 = 0 , r1 = min( step1 , step2 ) , cnt = 0; while( l1 <= r1 ){ ll mid = ( l1 + r1 ) / 2; a1 = a , b1 = b , c1 = c; ma1 = ma , mb1 = mb , mc1 = mc; tz( a1 , b1 , c1 , mid ); tz( ma1 , mb1 , mc1 , mid ); l[1] = ma1 , l[2] = mb1 , l[3] = mc1; sort( l + 1 , l + 3 + 1 ); s[1] = a1 , s[2] = b1 , s[3] = c1; sort( s + 1 , s + 3 + 1 ); bool fla = 0; for( int i = 1 ; i <= 3 ; i ++ ){ if( l[i] != s[i] ){ fla = 1; break; } } if(!fla ) r1 = mid - 1 , cnt = mid * 2; else l1 = mid + 1; } printf( "%lld" , cnt + ans ); return 0; }

有些细节要扣，注意一下

3.求和

思想

由于k很小，可以在dfs的时候把k次方打出来就行了

接着，可以引进前缀和差分的思想（就像树状数组与前缀和）

可以将a到b之间的路径拆成两部分：a到它们LCA的部分和b到它们LCA的部分。再用差分思想将每个部分看成是点到根的路径去掉LCA到根的路径，这样只需维护每个点到根的路径上所有点的权值之和，就可以求出答案。​

注意LCA本身的权值会被减两次，要补回来

代码：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> using namespace std; #define ll long long const int MAXN = 300003; const int Mod = 998244353; ll qz[MAXN][53]; int f[MAXN][23]; ll sz[MAXN][53]; int height[MAXN]; vector< int > G[MAXN]; int k , n , m; void read( int &x ){ x = 0; char s = getchar(); while( s < '0' || s > '9' ){ s = getchar(); } while( s >= '0' && s <= '9' ){ x = x * 10 + s - '0'; s = getchar(); } } ll qpow( ll x , ll y ){ ll sum = 1; while( y ){ if( y % 2 ) sum = sum * x % Mod; x = x * x % Mod; y /= 2; } return sum; } void dfs( int x , int fa1 ){ sz[x][0] = 1; for( int i = 1 ; i <= 50 ; i ++ ){ sz[x][i] = sz[x][i-1] * height[x] % Mod; qz[x][i] = ( ( qz[fa1][i] + sz[x][i] ) % Mod + Mod ) % Mod; } for( int i = 0 ; i < G[x].size() ; i ++ ){ int v = G[x][i]; if( v == fa1 ) continue; height[v] = height[x] + 1; f[v][0] = x; dfs( v , x ); } } void jump( int &x , int mu ){ for( int i = 20 ; i >= 0 ; i -- ) if( height[f[x][i]] >= mu ) x = f[x][i]; } int LCA( int x , int y ){ if( height[x] > height[y] ) jump( x , height[y] ); else if( height[x] < height[y] ) jump( y , height[x] ); if( x == y ) return x; for( int i = 20 ; i >= 0 ; i -- ){ if( f[x][i] != f[y][i] ) x = f[x][i] , y = f[y][i]; } return f[x][0]; } int main() { read( n ); for( int i = 1 ; i < n ; i ++ ){ int x , y; read( x );read( y ); G[x].push_back( y ); G[y].push_back( x ); } memset( height , -1 , sizeof( height ) ); height[1] = 0; dfs( 1 , 1 ); for( int j = 1 ; j <= 20 ; j ++ ) for( int i = 1 ; i <= n ; i ++ ) f[i][j] = f[f[i][j-1]][j-1]; read( m ); for( int i = 1 ; i <= m ; i ++ ){ int x , y; read( x );read( y );read( k ); int lca = LCA( x , y ); ll step = ( ( ( ( ( ( qz[x][k] - qz[lca][k] ) % Mod + Mod ) % Mod + ( ( qz[y][k] - qz[lca][k] ) % Mod + Mod ) % Mod) % Mod + Mod ) % Mod + sz[lca][k] ) % Mod + Mod )% Mod; printf( "%lld\n" , step ); } return 0; }

有些oj读优才卡过，注意取模

4.次小生成树 Tree

首先，我们可以很简单地求出最小生成树

这里我们求的是严格次小，所以一定有边与最小生成树不一样，但是大部分都是一样的

应该有n-2条边（总共n-1条）都是一样的，我们去枚举每一条没被选中的边，把这条边所连接的两个点a，b的树上路径中的严格最大权值算出来，再进行替换，这样依次枚举，就可以得到答案

现在的问题是什么是严格最大权值，怎么求呢？

就是大部分情况都是找最大值，但是如果我要替换的边是我现在找到的最大权值，那么我为了满足严格次小生成树，只能用次大边来进行替换了。

那么怎么做呢？

用倍增的思想。f[x][j]表示从第x个点开始一直向上跳步这段中所得到的最大权值

而次大权值也是这样做的，所以可以用结构体

f[x][0] 就为x到fa[x]的权值,

注意替换的一些细节，一定要很仔细，庆幸自己一遍就写对了

代码:

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> #include <algorithm> #include <climits> #define ll long long using namespace std; const int MAXN = 300003; int n , m; struct node{ int v ; ll w; node(){} node( int V , ll W ){ v = V; w = W; } }; struct edge{ int s , l; ll w; bool flag ; friend bool operator < ( edge a , edge b ){ return a.w < b.w; } }a[MAXN]; vector < node > G[MAXN]; int fa[MAXN]; int f[MAXN][23] ; int height[MAXN]; ll maxx[MAXN][23] , max1[MAXN][23]; ll p , k1; void read( ll &x ){ x = 0; char s = getchar(); while( s < '0' || s > '9' ){ s = getchar(); } while( s >= '0' && s <= '9' ){ x = x * 10 + s - '0'; s = getchar(); } } int findSet( int x ){ if( x != fa[x] ) fa[x] = findSet( fa[x] ); return fa[x]; } void dfs( int x , int fa1 ){ for( int i = 0 ; i < G[x].size() ; i ++ ){ int v = G[x][i].v , w = G[x][i].w; if(v == fa1 )continue; height[v] = height[x] + 1; f[v][0] = x; maxx[v][0] = w; dfs( v , x ); } } void jump( int &x , ll mu , ll &w , ll &w1 ){ for( int i = 19 ; i >= 0 ; i -- ){ if( height[f[x][i]] >= mu ){ if( w < maxx[x][i] ){ w1 = w; w = maxx[x][i]; } else if( w > maxx[x][i] ) w1 = max( w1 , maxx[x][i] ); w1 = max( w1 , max1[x][i] ); x = f[x][i]; } } } void LCA( int x , int y ){ if( height[x] > height[y] ) jump( x , height[y] , p , k1 ); else if( height[x] < height[y] ) jump( y , height[x] , p , k1 ); if( x == y ) return ; for( int i = 19 ; i >= 0 ; i -- ){ if( f[x][i] != f[y][i] ){ p = max( maxx[x][i] , p ); p = max( maxx[y][i] , p ); k1 = max( k1 , max1[x][i] ); k1 = max( k1 , max1[y][i] ); if( p > maxx[x][i] ) k1 = max( maxx[x][i] , k1 ); if( p > maxx[y][i] ) k1 = max( k1 , maxx[y][i] ); x = f[x][i] , y = f[y][i]; } } int i = 0; p = max( maxx[x][i] , p ); p = max( maxx[y][i] , p ); k1 = max( k1 , max1[x][i] ); k1 = max( k1 , max1[y][i] ); if( p > maxx[x][i] ) k1 = max( maxx[x][i] , k1 ); if( p > maxx[y][i] ) k1 = max( k1 , maxx[y][i] ); x = f[x][i] , y = f[y][i]; //printf( "%lld %lld\n" , p , k1 ); } int main(){ scanf( "%d%d" , &n , &m ); for( int i = 1; i <= m ; i ++ ) scanf( "%d%d" , &a[i].s , &a[i].l ) , read( a[i].w ); sort( a + 1 , a + m + 1 ); for( int i = 1 ; i <= n ; i ++ ) fa[i] = i; int k = 0 ; ll MST = 0; for( int i = 1 ; i <= m ; i ++ ){ int u = findSet( a[i].s ) , v = findSet( a[i].l ); if( u == v ) continue; k ++; fa[u] = v; MST += a[i].w; a[i].flag = 1; G[a[i].s].push_back(node( a[i].l , a[i].w ) ); G[a[i].l].push_back(node( a[i].s , a[i].w ) ); if( k == n - 1 ) break; } //printf( "%d" , MST ); height[1] = 1; dfs( 1 , 0 ); for( int j = 1 ; j <= 19 ; j ++ ) for( int i = 1 ; i <= n ; i ++ ){ f[i][j] = f[f[i][j-1]][j-1]; ll x = maxx[i][j-1] , y = maxx[f[i][j-1]][j-1]; maxx[i][j] = max( x , y ); max1[i][j] = max( max1[i][j-1] , max1[f[i][j-1]][j-1] ); if( x > y ) max1[i][j] = max( max1[i][j] , y ); else if( x < y ) max1[i][j] = max( max1[i][j] , x ); } ll sum = LLONG_MAX; for( int i = 1 ; i <= m ; i ++ ){ if( a[i].flag ) continue; p = 0 , k1 = 0; LCA( a[i].s , a[i].l ); if( a[i].w == p ) p = k1; if( MST + a[i].w - p < sum ) sum = MST + a[i].w - p; } printf( "%lld" , sum ); return 0; }

注意数组的大小与long long

5.松鼠的新家

同样用前缀和做，记得把LCA的父亲减一

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> #include <algorithm> #define ll long long using namespace std; const int MAXN = 300003; int n ; int f[MAXN][30]; int s[MAXN]; int sz[MAXN] , fa[MAXN]; vector< int > G[MAXN]; void dfs( int x , int fa1 ){ for( int i = 0 ; i < G[x].size() ; i ++ ){ int v = G[x][i]; if( fa1 == v ) continue; sz[v] = sz[x] + 1; fa[v] = x; f[v][0] = x; dfs( v , x ); } } void pre( ){ sz[1] = 1; dfs( 1 , 0 ); for( int j = 1 ; j <= 29 ; j ++ ) for( int i = 1 ; i <= n ; i ++ ) f[i][j] = f[f[i][j-1]][j-1]; } void jump( int &x , int mu ){ for( int i = 29 ; i >= 0 ; i -- ) if( sz[f[x][i]] >= mu ) x = f[x][i]; } int LCA( int x , int y ){ if( sz[x] > sz[y] ) jump( x , sz[y] ); else if( sz[x] < sz[y] ) jump( y , sz[x] ); if( x != y ){ for( int i = 29 ; i >= 0 ;i -- ) if( f[x][i] != f[y][i] ) x = f[x][i] , y = f[y][i]; x = f[x][0]; } return x; } int sum[MAXN]; void find_( int x , int fa1 ){ for( int i = 0 ; i < G[x].size() ; i ++ ){ int v = G[x][i]; if( v == fa1 ) continue; find_( v , x ); sum[x] += sum[v]; } } int main(){ scanf( "%d" , &n ); for( int i = 1; i <= n ; i ++ ) scanf( "%d" , &s[i] ); for( int i = 1 ; i < n ; i ++ ){ int x , y; scanf( "%d%d" , &x , &y ); G[x].push_back( y ); G[y].push_back( x ); } pre(); for( int i = 1 ; i < n ; i ++ ){ sum[s[i]] ++; sum[s[i+1]] ++; sum[ LCA( s[i] , s[i+1] ) ] -- ; sum[ f[LCA( s[i] , s[i+1] )][0] ] -= 1 ; } find_( 1 , 0 ); for( int i = 2 ; i <= n ; i ++ ) sum[s[i]] --; for( int i = 1 ; i < n ; i ++ ) printf( "%d\n" , sum[i] ); printf( "%d\n" , sum[n]) ; // printf( "%d" , sum[1] ); return 0; }

6.冷战

考虑到是否连通，且是在线的，所以果断选择并查集

但是这道题还要输出最短使a,b联通的时间

那么可以把时间看做一条权值，用一个数组维护，做并查集的时候看哪一边深度小就放在哪一边的数组里（用秩合并）：

void unionSet( int x , int y , int t ){ int u = findSet( x ) , v = findSet( y ); if( u == v ) return ; if( height[u] >= height[v] ){ fa[v] = u; sum[v] = t; if( height[u] == height[v] ) height[u] ++; } else{ sum[u] = t; fa[u] = v; } }

可为什么把权值这样存呢？其实如果x与y相连，且height[x]>height[y] 那么这条边就会一直存在,也就是说fa[y] = x

那么y的父亲不会再改变了，所以就可以存在y里。

那么现在怎么找最大值呢？

直接普通的LCA就可以了，且用的是现在并查集所得到的生成树做。

至于为甚么，其实也可以分类讨论

因为儿子不变，所以权值不变