C++ – 树上路径最大权

倍增思想

由 倍增 LCA 改的

lli mw[32][maxn];
lli fa[32][maxn];
lli dep[maxn];

void dfs_mw(lli u) {
    dep[u] = dep[fa[0][u]] + 1;
    for (lli i = 1; (1 << i) <= dep[u]; ++i)
        fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (lli i = 1; (1 << i) <= dep[u]; ++i)
        mw[i][u] = max(mw[i - 1][u], mw[i - 1][fa[i - 1][u]]);
    for (lli i = head[u]; ~i; i = edge[i].nxt) {
        lli v = edge[i].v;
        lli w = edge[i].w;
        if (v == fa[0][u]) continue;
        fa[0][v] = u;
        mw[0][v] = w;
        dfs_mw(v);
    }
}

lli ask_mw(lli x, lli y) {
    if (x == y) return 0;
    lli res = 0;
    if (dep[x] > dep[y]) swap(x, y);
    for (lli i = 24; i >= 0; --i) {
        if (dep[x] <= dep[y] - (1 << i)) {
            res = max(res, mw[i][y]);
            y = fa[i][y];
        }
    }
    if (x == y) return res;
    for (lli i = 24; i >= 0; --i) {
        if (fa[i][x] != fa[i][y]) {
            res = max(res, mw[i][x]);
            res = max(res, mw[i][y]);
            x = fa[i][x]; 
            y = fa[i][y];
        }   
    }
    res = max(res, max(mw[0][x], mw[0][y]));
    return res;
}