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 を探す方法も研究します。