Submission #768578

#	Time	Username	Problem	Language	Result	Execution time	Memory
768578		green_gold_dog	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	476 ms	86988 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll LOG = 20;

template<typename T>
bool assign_min(T& a, T b) {
        if (a > b) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_max(T& a, T b) {
        if (a < b) {
                a = b;
                return true;
        }
        return false;
}

struct DSU {
        vector<ll> p;
        DSU(ll n) {
                p.resize(n, 0);
                for (ll i = 0; i < n; i++) {
                        p[i] = i;
                }
        }
        ll get(ll x) {
                return (p[x] == x ? x : p[x] = get(p[x]));
        }
        void unite(ll a, ll b) {
                p[b] = a;
        }
};

struct LCA {
        vector<vector<ll>> tree;
        vector<ll> h;
        vector<vector<ll>> binup;
        LCA(vector<vector<ll>> tree): tree(tree) {
                ll n = tree.size();
                h.resize(n, -1);
                binup.resize(n, vector<ll>(LOG, 0));
                dfs(0, 0);
        }
        void dfs(ll v, ll p) {
                h[v] = h[p] + 1;
                binup[v][0] = p;
                for (ll i = 1; i < LOG; i++) {
                        binup[v][i] = binup[binup[v][i - 1]][i - 1];
                }
                for (auto i : tree[v]) {
                        if (i != p) {
                                dfs(i, v);
                        }
                }
        }
        ll la(ll v, ll x) {
                for (ll i = 0; i < LOG; i++) {
                        if ((x >> i) & 1) {
                                v = binup[v][i];
                        }
                }
                return v;
        }
        ll lca(ll v, ll u) {
                if (h[v] < h[u]) {
                        swap(v, u);
                }
                v = la(v, h[v] - h[u]);
                if (v == u) {
                        return v;
                }
                for (ll i = LOG - 1; i >= 0; i--) {
                        if (binup[v][i] != binup[u][i]) {
                                v = binup[v][i];
                                u = binup[u][i];
                        }
                }
                return binup[v][0];
        }
        ll dfs2(ll v, ll p, ll u, ll x) {
                if (v == u) {
                        return x;
                }
                for (auto i : tree[v]) {
                        if (i != p) {
                                ll a = dfs2(i, v, u, x + 1);
                                if (a != -1) {
                                        return a;
                                }
                        }
                }
                return -1;
        }
        ll dist(ll v, ll u) {
                return h[v] + h[u] - h[lca(v, u)] * 2;
        }
};

void solve() {
        ll n;
        cin >> n;
        vector<pair<ll, ll>> arr(n);
        for (ll i = 0; i < n; i++) {
                cin >> arr[i].first;
                arr[i].second = i;
        }
        sort(arr.begin(), arr.end());
        vector<vector<ll>> tree(n);
        for (ll i = 1; i < n; i++) {
                ll a, b;
                cin >> a >> b;
                a--;
                b--;
                tree[a].push_back(b);
                tree[b].push_back(a);
        }
        DSU d(n);
        LCA l(tree);
        l.dist(3, 4);
        vector<ll> dp(n, -1);
        ll ans = 0;
        for (auto[_, i] : arr) {
                dp[i] = 0;
                for (auto j : tree[i]) {
                        if (dp[j] >= 0) {
                                ll x = d.get(j);
                                assign_max(dp[i], dp[x] + l.dist(i, x));
                                d.unite(i, x);
                        }
                }
                ans = dp[i];
        }
        cout << ans << '\n';
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        solve();
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26