LightOJ - 1162 Min Max Roads

题解：在线倍增LCA和模拟ST表

让我们求从\(u->v\)最短路径上的边权最大值和边权最小值，那么我们可以利用倍增思想，类似其\(fa[u][i]\)数组代表从\(u\)往上跳\(2^i\)步的点这一思想，我们可以建立两个二维数组\(dmax[u][i]，dmin[u][i]\)，代表从\(u\)往上跳\(2^i\)步到达的点和\(u\)之间路径的最大权值和最小权值，同时我们可以知道dmax和dmin的初始状态：\(dmax[u][0]=dmin[u][0]=w_i\),最后类似\(fa[u][i] = fa[fa[u[i-1]]][i-1]\)我们列出状态方程：\(dmax[u][i]=max(dmax[u][i-1],dmax[fa[u][i-1]][i-1])\),\(dmin[u][i]=min(dmin[u][i-1],dmin[fa[u][i-1]][i-1])\),

这就类似ST表的思想，一个区间的最大值是可重复的贡献，所以我们各取区间的一半分别取\(max/min\)，所以这个方程就代表：从\(u\)往上跳\(2^i\)步到达的点和\(u\)之间路径的最大权值和最小权值，\([u,2^i] = max/min([u,2^{i-1}],[u+2^{i-1},u+2^i])\)

#include <bits/stdc++.h>

#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)

#define all(x) (x).begin(), (x).end()

#define endl '\n'

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

const double eps = 1e-9;

const int N = 1e5 + 10;

int n, m;

int fa[N][22], dmax[N][22], dmin[N][22];

int du[N], dep[N];

vector<pii> g[N];

void init()

{

    memset(fa, 0, sizeof fa);

    memset(dmax, 0, sizeof dmax);

    memset(dmin, 0, sizeof dmin);

    for (int i = 1; i <= n; ++i)

        du[i] = 0, dep[i] = 0, g[i].clear();

}

void dfs(int u, int par, int w)

{

    dep[u] = dep[par] + 1;

    fa[u][0] = par;

    dmax[u][0] = w;

    dmin[u][0] = w;

    for (int i = 1; i <= 20; ++i)

    {

        fa[u][i] = fa[fa[u][i - 1]][i - 1];

        dmax[u][i] = max(dmax[u][i - 1], dmax[fa[u][i - 1]][i - 1]);

        dmin[u][i] = min(dmin[u][i - 1], dmin[fa[u][i - 1]][i - 1]);

    }

    for (auto &[v, W] : g[u])

    {

        if (v == par)

            continue;

        dfs(v, u, W);

    }

}

void lca(int u, int v)

{

    int maxx = -inf, minn = inf;

    if (dep[u] < dep[v])

        swap(u, v);

    for (int i = 20; i >= 0; i--)

    {

        if (dep[fa[u][i]] >= dep[v])

        {

            maxx = max(maxx, dmax[u][i]);       //注意一定要先去取区间max和min，不然u就会改变

            minn = min(minn, dmin[u][i]);

            u = fa[u][i];

        }

    }

    if (u == v)

    {

        cout << minn << " " << maxx << endl;

        return;

    }

    for (int i = 20; i >= 0; --i)

    {

        if (fa[u][i] != fa[v][i])

        {

            maxx = max({maxx, dmax[u][i], dmax[v][i]});

            minn = min({minn, dmin[u][i], dmin[v][i]});

            u = fa[u][i], v = fa[v][i];

        }

    }

    maxx = max({maxx, dmax[u][0], dmax[v][0]});

    minn = min({minn, dmin[u][0], dmin[v][0]});

    cout << minn << " " << maxx << endl;

}

int main(void)

{

    Zeoy;

    int t = 1;

    cin >> t;

    int tot = 1;

    while (t--)

    {

        cin >> n;

        cout << "Case " << tot++ << ":\n";

        init();

        for (int i = 1, u, v, w; i < n; ++i)

        {

            cin >> u >> v >> w;

            du[v]++;

            g[u].push_back({v, w});

            g[v].push_back({u, w});

        }

        int st;

        for (int i = 1; i <= n; ++i)

        {

            if (du[i] == 0)

            {

                st = i;

                break;

            }

        }

        dfs(st, 0, 0);

        cin >> m;

        for (int i = 1, u, v; i <= m; ++i)

        {

            cin >> u >> v;

            lca(u, v);

        }

    }

    return 0;

}

巴特西

LightOJ - 1162 Min Max Roads

LightOJ - 1162 Min Max Roads

题解：在线倍增LCA和模拟ST表

最新文章

热门文章