/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 324.0 KiB
#2 Accepted 2ms 532.0 KiB
#3 Accepted 2ms 324.0 KiB
#4 Accepted 2ms 328.0 KiB
#5 Accepted 2ms 324.0 KiB
#6 Accepted 2ms 532.0 KiB
#7 Accepted 15ms 1.016 MiB
#8 Accepted 16ms 1004.0 KiB
#9 Accepted 15ms 1.051 MiB
#10 Accepted 15ms 1.051 MiB
#11 Accepted 477ms 12.137 MiB
#12 Accepted 464ms 12.184 MiB
#13 Accepted 458ms 12.137 MiB
#14 Accepted 467ms 12.18 MiB
#15 Accepted 292ms 2.973 MiB
#16 Accepted 294ms 2.773 MiB
#17 Accepted 287ms 2.93 MiB
#18 Accepted 287ms 2.98 MiB
#19 Accepted 284ms 2.945 MiB
#20 Accepted 292ms 2.973 MiB

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define nl '\n'

typedef pair<int, int> pii;
struct info
{
    ll sum = 0;
};

struct segtree
{
    int n;
    vector<info> t;

    void init(int n, vector<ll> &a)
    {
        t.clear();
        this->n = n;
        t.resize(n * 4);
        build(1, 0, n - 1, a);
    }
    info Merge(info l, info r)
    {
        info ret;
        ret.sum = max(l.sum, r.sum);
        return ret;
    }
    void build(int node, int l, int r, vector<ll> &a)
    {
        if (l == r)
        {
            t[node].sum = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(node * 2, l, mid, a);
        build(node * 2 + 1, mid + 1, r, a);
        t[node] = Merge(t[node * 2], t[node * 2 + 1]);
    }

    info query(int node, int l, int r, int i, int j)
    {
        if (l > j || r < i)
        {
            info nul;
            return nul;
        }
        if (l >= i && r <= j)
            return t[node];
        int mid = (l + r) / 2;
        return Merge(query(node * 2, l, mid, i, j), query(node * 2 + 1, mid + 1, r, i, j));
    }
    ll query(int l, int r)
    {
        auto ret = query(1, 0, n - 1, l, r);
        return ret.sum;
    }
};

struct HLD
{
    vector<int> parent, depth, heavy, head, pos;
    int cur_pos;
    segtree seg;
    int dfs(int v, vector<vector<pii>> const &adj, vector<ll> &a)
    {
        int size = 1;
        int max_c_size = 0;
        for (auto [c, w] : adj[v])
        {
            if (c != parent[v])
            {
                a[c] = w;
                parent[c] = v, depth[c] = depth[v] + 1;
                int c_size = dfs(c, adj, a);
                size += c_size;
                if (c_size > max_c_size)
                    max_c_size = c_size, heavy[v] = c;
            }
        }
        return size;
    }

    void decompose(int v, int h, vector<vector<pii>> const &adj)
    {
        head[v] = h, pos[v] = cur_pos++;
        if (heavy[v] != -1)
            decompose(heavy[v], h, adj);
        for (auto xx : adj[v])
        {
            int c = xx.first;
            if (c != parent[v] && c != heavy[v])
                decompose(c, c, adj);
        }
    }

    void init(vector<vector<pii>> const &adj)
    {
        int n = adj.size();
        parent = vector<int>(n);
        depth = vector<int>(n);
        heavy = vector<int>(n, -1);
        head = vector<int>(n);
        pos = vector<int>(n);
        cur_pos = 0;

        vector<ll> tmp(n), a(n);

        dfs(0, adj, a);
        decompose(0, 0, adj);

        for (int i = 0; i < n; i++)
            tmp[pos[i]] = a[i];
        seg.init(n, tmp);
    }

    ll query(int a, int b)
    {
        ll res = 0;
        for (; head[a] != head[b]; b = parent[head[b]])
        {
            if (depth[head[a]] > depth[head[b]])
                swap(a, b);
            ll cur_heavy_path_max = seg.query(pos[head[b]], pos[b]);
            res = max(res, cur_heavy_path_max);
        }
        if (depth[a] > depth[b])
            swap(a, b);
        ll last_heavy_path_max = seg.query(pos[a] + 1, pos[b]);
        res = max(res, last_heavy_path_max);
        return res;
    }
};

int main() {
    int n, q; cin >> n >> q;
    vector<vector<pii>> adj;
    adj.resize(n);
    for(int i=0;i<n-1;++i){
        int u,v,w; cin >> u >> v >> w; u--,v--;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    HLD hd;
    hd.init(adj);
    while(q--){
        int u,v; cin >> u >> v; u--,v--;
        cout << hd.query(u,v) << nl;
    }
}

Information

Submit By
Type
Submission
Problem
P1019 Graph Stuff
Contest
Sylhet ICPC 2024 Collaborative Challenge: Episode 2
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-30 10:56:38
Judged At
2024-11-11 02:35:01
Judged By
Score
100
Total Time
477ms
Peak Memory
12.184 MiB