lca

void dfs(int x,int fr,LL fw){ //start with dfs(1,0,0) if vertex is 1-base
    if (fr){
        dep[x] = dep[fr] + 1;
        anc[x][0] = make_pair(fr,fw);
        for (int i=1;i<=__lg(dep[x]);++i){
            int i_anc = anc[x][i-1].F;
            anc[x][i] = make_pair(anc[i_anc][i-1].F,max(anc[i_anc][i-1].S,anc[x][i-1].S));
        }
    }

    for (auto [t,w]:tree[x]){
        if (t != fr)
            dfs(t,x,w);
    }
}

LL lca(int u,int v){
    LL ret = 0;
    if (dep[v] > dep[u])
        swap(u,v);
    if (dep[u] > dep[v]){
        int k = dep[u] - dep[v];
        for (int i=0;i<=__lg(k);++i){
            if ((1 << i) & k){
                ret = max(ret,anc[u][i].S);
                u = anc[u][i].F;
            }
        }
    }
    if (u == v)
        return ret;

    for (int i=__lg(dep[u]);i>=0;--i){
        if (anc[u][i].F != anc[v][i].F){
            ret = max(ret,max(anc[u][i].S,anc[v][i].S));
            u = anc[u][i].F;
            v = anc[v][i].F;
        }
    }
    ret = max(ret,max(anc[u][0].S,anc[v][0].S));

    return ret;
}