Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target("avx,avx2")
- #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native")
- #pragma GCC optimize("03")
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <numeric>
- #include <algorithm>
- #include <unordered_set>
- #include <unordered_map>
- #include <set>
- #include <map>
- #include <queue>
- #include <deque>
- #include <bitset>
- #include <stack>
- #include <random>
- #define pb push_back
- #define ll long long
- #define ld long double
- #define all(a) a.begin(), a.end()
- #define sz(a) (int)a.size()
- using namespace std;
- //tg: @galebickosikasa
- const int maxn = (int)3e5;
- const int inf = (int)2e9;
- const ld eps = 1e-9;
- mt19937 SuperRandom;
- vector<pair<int, int>> order;
- vector<int> d, first_icon;
- struct SparseTable{
- vector<vector<pair<int, int>>> st;
- vector<int> pow;
- SparseTable(){
- int j = 1;
- while (1<<j < sz(order)) ++j;
- st = vector<vector<pair<int, int>>> (j, vector<pair<int, int>> (sz(order)));
- pow = vector<int> (sz(order) + 1);
- int tmp = 0;
- for (int i = 0; i < sz(order); ++i){
- st[0][i] = order[i];
- if (1<<(tmp + 1) <= i) ++tmp;
- pow[i] = tmp;
- }
- pow[sz(order)] = j - 1;
- for (int k = 1; k < j; ++k){
- for (int i = 0; i < sz(order); ++i){
- st[k][i] = min(st[k - 1][i], st[k - 1][i + (1<<(k - 1))]);
- }
- }
- }
- int get(int l, int r) const {
- if (l > r) swap(l, r);
- int k = pow[r - l + 1];
- return min(st[k][l], st[k][r - (1<<k) + 1]).second;
- }
- };
- int lca(int v, int u, const SparseTable& t){
- return t.get(first_icon[u], first_icon[v]);
- }
- void dfs(int v, vector<int>& used, const vector<vector<int>>& G, int deaph = 0){
- order.pb({deaph, v});
- d[v] = deaph;
- used[v] = 1;
- for (auto& u: G[v]){
- if (used[u]) continue;
- dfs(u, used, G, deaph + 1);
- order.pb({deaph, v});
- }
- }
- void kek(const SparseTable& goo, const vector<vector<int>>& G){
- int max_ans = 1, v = 1;
- cout << 1 << '\n';
- for (int i = 2; i < sz(G); ++i){
- int dist = d[i] + d[v] - d[lca(i, v, goo)];
- if (d[i] > d[v]){
- v = i;
- }
- if (dist > max_ans){
- max_ans = dist;
- if (d[i] > )
- }
- }
- }
- int main(){
- ios_base::sync_with_stdio(false);
- cout.tie(nullptr);
- cin.tie(nullptr);
- int n;
- cin >> n;
- vector<vector<int>> G(n);
- for (int i = 0; i < n; ++i){
- int v;
- cin >> v;
- if (i == 0) continue;
- --v;
- G[v].pb(i), G[i].pb(v);
- }
- vector<int> used(n, 0);
- d = vector<int> (n);
- first_icon = vector<int> (n, -1);
- for (int i = 0; i < sz(order); ++i)
- if (first_icon[order[i].second] == -1)
- first_icon[order[i].second] = i;
- dfs(0, used, G);
- SparseTable goo;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement