Original link: https://blog.chungzh.cn/articles/cf-342e/
CF342E Xenia and Tree
meaning of the title
Given a tree of $n$ nodes, initially node 1 is red and the rest are blue.
The following operations are required to be supported:
- Turn a node red.
- Ask the distance of node $u$ to the nearest red node.
A total of $q$ operations.
$1 \le n, q \le 10 ^5$
analyze
First of all we have two violent ideas:
- Every time a point turns red, start BFS from that point, and update the minimum value of its surrounding nodes until it cannot be updated.
- For each inquiry, LCA is calculated with the previous red point, the distance is calculated, and the minimum value is taken.
Neither approach will work. But we can combine them, which is called divide and conquer (aka operation chunking).
We divide the operation sequence into blocks with $\sqrt m$ as the block length. For a query, there are two cases:
- Modifications within the same block and prior to the query can brute force LCA to find the distance.
- For the modification of the previous block, the answer for each point can be updated by multi-source BFS starting from the red point of the modification in the block after processing that block.
The final answer is to take the minimum of the two cases.
Probably $O((n+m)\sqrt m)$? I don’t actually count, but it’s pretty fast .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
|
#include <bits/stdc++.h> using namespace std ; const int MAXN = 100005 ; const int LOGN = 17 ; int n , m ; int f [ MAXN ][ LOGN ], depth [ MAXN ]; int tmpdis [ MAXN ]; vector < int > g [ MAXN ]; void dfs ( int cur , int father ) { depth [ cur ] = depth [ father ] + 1 ; f [ cur ][ 0 ] = father ; for ( int i = 1 ; i < LOGN ; i ++ ) f [ cur ][ i ] = f [ f [ cur ][ i - 1 ]][ i - 1 ]; for ( int i = 0 ; i < g [ cur ]. size (); i ++ ) { if ( g [ cur ][ i ] == father ) continue ; dfs ( g [ cur ][ i ], cur ); } } int lca ( int u , int v ) { if ( depth [ u ] > depth [ v ]) swap ( u , v ); for ( int i = LOGN - 1 ; i >= 0 ; i -- ) { if ( depth [ f [ v ][ i ]] >= depth [ u ]) v = f [ v ][ i ]; } for ( int i = LOGN - 1 ; i >= 0 ; i -- ) { int s = f [ u ][ i ], t = f [ v ][ i ]; if ( s != t ) { u = s ; v = t ; } } if ( u != v ) return f [ u ][ 0 ]; return u ; } int dist ( int u , int v ) { int l = lca ( u , v ); return depth [ u ] + depth [ v ] - 2 * depth [ l ]; } int main () { scanf ( "%d%d" , & n , & m ); for ( int i = 0 ; i < n - 1 ; i ++ ) { int u , v ; scanf ( "%d%d" , & u , & v ); g [ u ]. push_back ( v ); g [ v ]. push_back ( u ); } dfs ( 1 , 1 ); int b = sqrt ( m ); vector < int > buf ; memset ( tmpdis , 0x3f , sizeof tmpdis ); buf . push_back ( 1 ); for ( int i = 0 ; i < m ; i ++ ) { int type , v ; scanf ( "%d%d" , & type , & v ); if ( type == 1 ) { buf . push_back ( v ); } else { // 之前块的答案记在tmpdis 中int ans = tmpdis [ v ]; for ( int i = 0 ; i < buf . size (); i ++ ) ans = min ( ans , dist ( v , buf [ i ])); // 当前块直接暴力LCA printf ( "%d \n " , ans ); } if ( i % b == 0 ) { queue < int > q ; for ( int i = 0 ; i < buf . size (); i ++ ) { q . push ( buf [ i ]); tmpdis [ buf [ i ]] = 0 ; } buf . clear (); // BFS 记录答案while ( ! q . empty ()) { int f = q . front (); q . pop (); for ( int i = 0 ; i < g [ f ]. size (); i ++ ) { if ( tmpdis [ g [ f ][ i ]] > tmpdis [ f ] + 1 ) { tmpdis [ g [ f ][ i ]] = tmpdis [ f ] + 1 ; q . push ( g [ f ][ i ]); } } } } } return 0 ; }
|
Reference: [CF342E] Xenia and Tree – block, ST table, LCA – Mollnn – Blog Park
@ 2022/10/6 SM Demo.
This article is reproduced from: https://blog.chungzh.cn/articles/cf-342e/
This site is for inclusion only, and the copyright belongs to the original author.