Lowest common ancestor
I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries:
1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 basic things should always be recorded:
a. pre[ k ]: which node was visited when timestamp was k.
b. in[ u ]: the first timestamp when visiting node u.
c. depth[ k ]: the depth of the node visiting when timestamp was k.
2. Notice that for a query ( u, v ), lca( u, v ) is in the set of nodes that were visited sometime between the two timestamps in[ u ] and in[ v ]. Precisely, lca( u, v ) is the node that possesses the minimum depth, that was visited between the two timestamps. So we will initialize a data structure that supports fast query for range minimum. Here I use Sparse table, for its time complexity for query is constant time. Don't forget to convert the timestamp to the id of the node at last.
1986 -- Distance Queries
Given a tree, and cost for each edge, answer for each query ( u, v ), the cost for the path u <-> v.
This is a classical problem. Let mdis[ i ] = cost from root to node i, then the answer for any query will be mdis[ u ] + mdis[ v ] - 2 * mdis[ lca( u, v ) ].
#include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef pair<int, int> pii; const int MAXN = 5e4 + 10; int n, m; vector<pii> G[MAXN]; int dfs_clock; // [ 1, 2 * n - 1 ] int pre[MAXN << 1], depth[MAXN << 1], in[MAXN]; int mdis[MAXN]; // distance from root void dfs(int u, int fa, int d){ pre[ ++dfs_clock ] = u; in[ u ] = dfs_clock; depth[ dfs_clock ] = d; for(int i = 0; i < G[u].size(); ++i){ pii &e = G[u][i]; if( e.second == fa ) continue; mdis[ e.second ] = mdis[ u ] + e.first; dfs( e.second, u, d + 1 ); pre[ ++dfs_clock ] = u; depth[ dfs_clock ] = d; } } struct SparseTable{ // min by depth[ i ], but return i for query pii st[20][MAXN << 1]; // st[ i ][ j ]: pii of min depth in [ j, j + 2^i ) void init(int n){ for(int i = 1; i <= n; ++i) st[0][i] = pii( depth[i], i ); for(int i = 1; ( 1 << i ) <= n; ++i) for(int j = 1; j + ( 1 << i ) - 1 <= n; ++j) st[i][j] = min( st[i - 1][j], st[i - 1][j + ( 1 << i - 1 )] ); } int query(int ql, int qr){ int k = 31 - __builtin_clz( qr - ql + 1 ); // first non-zero from left in binary // int k = 0; while( ( qr - ql + 1 ) >> k ) ++k; --k; // this is an alternative return min( st[k][ql], st[k][qr - ( 1 << k ) + 1] ).second; } } Rmq; void predo(){ dfs_clock = 0; dfs( 1, -1, 0 ); Rmq.init( 2 * n - 1 ); // there are always exactly 2 * |V| - 1 timestamps } int lca(int u, int v){ if( in[ u ] > in[ v ] ) swap( u, v ); int clock_of_min_depth = Rmq.query( in[ u ], in[ v ] ); return pre[ clock_of_min_depth ]; } int main(){ while( scanf("%d%d", &n, &m) == 2 ){ for(int u = 1; u <= n; ++u) G[u].clear(); while( m-- ){ int u, v, c; char _[3]; scanf("%d%d%d%s", &u, &v, &c, _); G[u].push_back( pii( c, v ) ); G[v].push_back( pii( c, u ) ); } predo(); int q; scanf("%d", &q); while( q-- ){ int u, v; scanf("%d%d", &u, &v); int ans = mdis[ u ] + mdis[ v ] - 2 * mdis[ lca( u, v ) ]; printf("%d\n", ans); } } return 0; }
2763 -- Housewife Wind
n nodes, each edge has its cost w, in the beginning you are on the s'th node, answer the queries:
a. the cost from the current position to another vertex x
b. change the cost of the x'th edge to t
1 <= n = 1e5, 0 <= q <= 1e5, 1 <= a[i], b[i] <= n, 1 <= w[i] <= 1e4
... すみません、呆気なく諦めました、RMQに回してからBITとかで弄ればいいはずなんですが、頑張ってもデバッグ出せず。Heavy Light Decomposition 学習した後それでこれを解いて見ます。HL でLCA を探す方法も研究します。