結果
問題 | No.2634 Tree Distance 3 |
ユーザー |
![]() |
提出日時 | 2024-02-16 22:40:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 710 ms / 3,000 ms |
コード長 | 4,314 bytes |
コンパイル時間 | 3,080 ms |
コンパイル使用メモリ | 213,532 KB |
実行使用メモリ | 35,984 KB |
最終ジャッジ日時 | 2024-09-28 21:17:07 |
合計ジャッジ時間 | 27,027 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 69 |
ソースコード
#pragma GCC optimize("O2") #include <algorithm> #include <array> #include <bit> #include <bitset> #include <cassert> #include <cctype> #include <cfenv> #include <cfloat> #include <chrono> #include <cinttypes> #include <climits> #include <cmath> #include <compare> #include <complex> #include <concepts> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <initializer_list> #include <iomanip> #include <ios> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <map> #include <memory> #include <new> #include <numbers> #include <numeric> #include <ostream> #include <queue> #include <random> #include <ranges> #include <set> #include <span> #include <sstream> #include <stack> #include <streambuf> #include <string> #include <tuple> #include <type_traits> #include <variant> //#define int ll #define INT128_MAX (__int128)(((unsigned __int128) 1 << ((sizeof(__int128) * __CHAR_BIT__) - 1)) - 1) #define INT128_MIN (-INT128_MAX - 1) #define clock chrono::steady_clock::now().time_since_epoch().count() #ifdef DEBUG #define dbg(x) cout << (#x) << " = " << x << '\n' #else #define dbg(x) #endif namespace R = std::ranges; namespace V = std::views; using namespace std; using ll = long long; using ull = unsigned long long; using ldb = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; //#define double ldb template<class T> ostream& operator<<(ostream& os, const pair<T, T> pr) { return os << pr.first << ' ' << pr.second; } template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N> &arr) { for(const T &X : arr) os << X << ' '; return os; } template<class T> ostream& operator<<(ostream& os, const vector<T> &vec) { for(const T &X : vec) os << X << ' '; return os; } template<class T> ostream& operator<<(ostream& os, const set<T> &s) { for(const T &x : s) os << x << ' '; return os; } struct fastJump { vector<int> p, jp, dep; fastJump(vector<vector<int>> g, int root = 0) : p(ssize(g)), jp(ssize(g)), dep(ssize(g)) { auto dfs = [&](int v, auto self) -> void { if (dep[p[v]] + dep[jp[jp[p[v]]]] == 2 * dep[jp[p[v]]]) jp[v] = jp[jp[p[v]]]; else jp[v] = p[v]; for(int x : g[v]) { if (x == p[v]) continue; p[x] = v, dep[x] = dep[v] + 1; self(x, self); } }; p[root] = jp[root] = root; dfs(root, dfs); } int jump(int v, int k) { k = min(k, dep[v]); while(k) { if (int d = dep[v] - dep[jp[v]]; d <= k) v = jp[v], k -= d; else v = p[v], k -= 1; } return v; } int lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); u = jump(u, dep[u] - dep[v]); if (u == v) return u; while(p[u] != p[v]) { if (jp[u] != jp[v]) u = jp[u], v = jp[v]; else u = p[u], v = p[v]; } return p[u]; } int kth(int s, int t, int k) { int m = lca(s, t); if (dep[s] + dep[t] - 2 * dep[m] < k) return -1; else if (dep[s] - dep[m] >= k) return jump(s, k); else return jump(t, dep[s] + dep[t] - 2 * dep[m] - k); } int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } }; signed main() { ios::sync_with_stdio(false), cin.tie(NULL); int n; cin >> n; vector<int> a(n); for(int &x : a) cin >> x; vector<vector<int>> g(n); for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; u--, v--; g[u].emplace_back(v); g[v].emplace_back(u); } fastJump fj(g); vector<int> ord(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int i, int j) { return a[i] > a[j]; }); int l = ord[0], r = ord[0], d = 0; vector<int> ans(n); for(int i = 1, p = 0; i <= n; i++) { if (i == n or a[ord[i]] != a[ord[i - 1]]) { for(int j = p; j < i; j++) { int x = fj.dis(ord[j], l); int y = fj.dis(ord[j], r); if (x >= y and x > d) r = ord[j], d = x; else if (x < y and y > d) l = ord[j], d = y; } for(int j = p; j < i; j++) ans[ord[j]] = max(fj.dis(l, ord[j]), fj.dis(r, ord[j])); p = i; } } cout << ans << '\n'; return 0; }