Language: C++

//#include <bits/stdc++.h>

#include <algorithm>
#include <vector>
#include <fstream>
#include <iostream>
#include <cassert>

#decine MAX_N 200000

#decine xx first
#decine yy second

using namespace std;

ifstream cin("in.txt");
ofstream cout("out.txt");

int n;
int v[MAX_N + 1];

int K;

struct aint
{
    int st, dr, mx;
};

aint arb[MAX_N * 4 + MAX_N * 20 + 1];

int root[MAX_N + 1];

vector <int> g[MAX_N + 1];

void add(int a, int b)
{
    g[a].push_back(b);
}

pair<int, int> x[MAX_N + 1];

void readFile()
{
    cin >> n;
    for(int i = 1; i<= n; i ++)
    {
        cin >> x[i].xx;
        x[i].yy = i;
    }

    sort(x + 1, x + n + 1);

    int cr = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(x[i].xx != x[i - 1].xx)
            cr ++;

        v[x[i].yy] = cr;
    }
/*
    for(int i = 1; i<= n; i ++)
        cout <<v[i] << " ";
    cout << "\n";*/

    for(int i = 1; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
}

void aloca(int &a)
{
    if(a != 0)
        return;

    ++ K;
    a = K;
}

int tata[MAX_N + 1];

int k;
int dfn[MAX_N  + 1];

void dfs(int a, int t)
{
    dfn[++ k] = a;
    tata[a] = t;

    for(auto u : g[a])
    {
        if(u != t)
        {
            dfs(u, a);
        }
    }
}

void build(int poz, int st, int dr, int a, int val)
{
    if(st == a && dr == a)
    {
        arb[poz].mx = val;

        return;
    }

    int mid = (st + dr) >> 1;

    if(a <= mid)
    {
        if(arb[poz].st == 0)
        {
            K ++;
            arb[poz].st = K;
        }

        build(arb[poz].st, st, mid, a, val);
    }

    else
    {
        if(arb[poz].dr == 0)
        {
            K ++;
            arb[poz].dr = K;
        }
        build(arb[poz].dr, mid + 1, dr, a, val);
    }

    arb[poz].mx = max(arb[arb[poz].st].mx, arb[arb[poz].dr].mx);
}

int getMax(int poz, int st, int dr, int a, int b)
{
    if(poz == 0)
        return 0;

    if(st == a && dr == b)
    {
        return arb[poz].mx;
    }

    int mid = (st + dr ) >> 1;

    if(b <= mid)
        return getMax(arb[poz].st, st, mid, a, b);

    if(a > mid)
        return getMax(arb[poz].dr, mid + 1, dr, a, b);

    if(a <= mid && b > mid)
    {
        int v1 = getMax(arb[poz].st, st, mid, a, mid);
        int v2 = getMax(arb[poz].dr, mid + 1, dr, mid + 1, b);

        return max(v1, v2);
    }

    assert(1 == 0);

    return 0;
}

int upd(int poz2, int st, int dr, int a, int val)
{
    ++ K;
    int poz1 = K;
    if(st == a && dr == a)
    {
        arb[poz1].mx = max(val, arb[poz2].mx);
        arb[poz1].st = arb[poz2].st;
        arb[poz1].dr = arb[poz2].dr;

        return poz1;
    }

    int mid = (st + dr) >> 1;

    if(a <= mid)
    {
        arb[poz1].st = upd(arb[poz2].st , st, mid, a, val);

        arb[poz1].dr = arb[poz2].dr;
    }

    else
    {
        arb[poz1].dr = upd(arb[poz2].dr , mid + 1, dr, a, val);

        arb[poz1].st = arb[poz2].st;
    }

    arb[poz1].mx = max({arb[arb[poz1].st].mx, arb[arb[poz1].dr].mx, arb[arb[poz2].st].mx, arb[arb[poz2].dr].mx});

    return poz1;
}

int rz[MAX_N + 1];

void solve()
{
    dfs(1, -1);

    cout << "1\n";

    aloca(root[1]);
    for(int i = 1; i <= n; i ++)
        build(root[1], 1, n, i, 0);

    build(root[1], 1, n, v[1], 1);

    for(int j = 2; j <= n; j ++)
    {
        int i = dfn[j];

        int rez = getMax(root[tata[i]], 1, n, 1, v[i] - 1) + 1;
        root[i] = upd(root[tata[i]], 1, n, v[i], rez);

        rz[i] = max(rez, rz[tata[i]]);
    }

    for(int i = 2; i <= n; i ++)
        cout << rz[i] << "\n";
}

int main()
{
    readFile();

    solve();


    return 0;
}


Compiler output:
a.cc:9:2: error: invalid preprocessing directive #decine; did you mean #define?
    9 | #decine MAX_N 200000
      |  ^~~~~~
      |  define
a.cc:11:2: error: invalid preprocessing directive #decine; did you mean #define?
   11 | #decine xx first
      |  ^~~~~~
      |  define
a.cc:12:2: error: invalid preprocessing directive #decine; did you mean #define?
   12 | #decine yy second
      |  ^~~~~~
      |  define
a.cc:20:7: error: 'MAX_N' was not declared in this scope
   20 | int v[MAX_N + 1];
      |       ^~~~~
a.cc:29:10: error: 'MAX_N' was not declared in this scope
   29 | aint arb[MAX_N * 4 + MAX_N * 20 + 1];
      |          ^~~~~
a.cc:29:22: error: 'MAX_N' was not declared in this scope
   29 | aint arb[MAX_N * 4 + MAX_N * 20 + 1];
      |                      ^~~~~
a.cc:31:10: error: 'MAX_N' was not declared in this scope
   31 | int root[MAX_N + 1];
      |          ^~~~~
a.cc:33:16: error: 'MAX_N' was not declared in this scope
   33 | vector <int> g[MAX_N + 1];
      |                ^~~~~
a.cc: In function 'void add(int, int)':
a.cc:37:5: error: 'g' was not declared in this scope
   37 |     g[a].push_back(b);
      |     ^
a.cc: At global scope:
a.cc:40:18: error: 'MAX_N' was not declared in this scope
   40 | pair<int, int> x[MAX_N + 1];
      |                  ^~~~~
a.cc: In function 'void readFile()':
a.cc:44:5: error: reference to 'cin' is ambiguous
   44 |     cin >> n;
      |     ^~~
In file included from a.cc:6:
/usr/include/c++/14/iostream:62:18: note: candidates are: 'std::istream std::cin'
   62 |   extern istream cin;           ///< Linked to standard input
      |                  ^~~
a.cc:16:10: note:                 'std::ifstream cin'
   16 | ifstream cin("in.txt");
      |          ^~~
a.cc:47:9: error: reference to 'cin' is ambiguous
   47 |         cin >> x[i].xx;
      |         ^~~
/usr/include/c++/14/iostream:62:18: note: candidates are: 'std::istream std::cin'
   62 |   extern istream cin;           ///< Linked to standard input
      |                  ^~~
a.cc:16:10: note:                 'std::ifstream cin'
   16 | ifstream cin("in.txt");
      |          ^~~
a.cc:47:16: error: 'x' was not declared in this scope
   47 |         cin >> x[i].xx;
      |                ^
a.cc:51:10: error: 'x' was not declared in this scope
   51 |     sort(x + 1, x + n + 1);
      |          ^
a.cc:59:9: error: 'v' was not declared in this scope
   59 |         v[x[i].yy] = cr;
      |         ^
a.cc:69:9: error: reference to 'cin' is ambiguous
   69 |         cin >> a >> b;
      |         ^~~
/usr/include/c++/14/iostream:62:18: note: candidates are: 'std::istream std::cin'
   62 |   extern istream cin;           ///< Linked to standard input
      |                  ^~~
a.cc:16:10: note:                 'std::ifstream cin'
   16 | ifstream cin("in.txt");
      |          ^~~
a.cc: At global scope:
a.cc:84:10: error: 'MAX_N' was not declared in this scope
   84 | int tata[MAX_N + 1];
      |          ^~~~~
a.cc:87:9: error: 'MAX_N' was not declared in this scope
   87 | int dfn[MAX_N  + 1];
      |         ^~~~~
a.cc: In function 'void dfs(int, int)':
a.cc:91:5: error: 'dfn' was not declared in this scope; did you mean 'dfs'?
   91 |     dfn[++ k] = a;
      |     ^~~
      |     dfs
a.cc:92:5: error: 'tata' was not declared in this scope
   92 |     tata[a] = t;
      |     ^~~~
a.cc:94:18: error: 'g' was not declared in this scope
   94 |     for(auto u : g[a])
      |                  ^
a.cc: In function 'void build(int, int, int, int, int)':
a.cc:107:9: error: 'arb' was not declared in this scope
  107 |         arb[poz].mx = val;
      |         ^~~
a.cc:116:12: error: 'arb' was not declared in this scope
  116 |         if(arb[poz].st == 0)
      |            ^~~
a.cc:122:15: error: 'arb' was not declared in this scope
  122 |         build(arb[poz].st, st, mid, a, val);
      |               ^~~
a.cc:127:12: error: 'arb' was not declared in this scope
  127 |         if(arb[poz].dr == 0)
      |            ^~~
a.cc:132:15: error: 'arb' was not declared in this scope
  132 |         build(arb[poz].dr, mid + 1, dr, a, val);
      |               ^~~
a.cc:135:5: error: 'arb' was not declared in this scope
  135 |     arb[poz].mx = max(arb[arb[poz].st].mx, arb[arb[poz].dr].mx);
      |     ^~~
a.cc: In function 'int getMax(int, int, int, int, int)':
a.cc:145:16: error: 'arb' was not declared in this scope
  145 |         return arb[poz].mx;
      |                ^~~
a.cc:151:23: error: 'arb' was not declared in this scope
  151 |         return getMax(arb[poz].st, st, mid, a, b);
      |                       ^~~
a.cc:154:23: error: 'arb' was not declared in this scope
  154 |         return getMax(arb[poz].dr, mid + 1, dr, a, b);
      |                       ^~~
a.cc:158:25: error: 'arb' was not declared in this scope
  158 |         int v1 = getMax(arb[poz].st, st, mid, a, mid);
      |                         ^~~
a.cc: In function 'int upd(int, int, int, int, int)':
a.cc:175:9: error: 'arb' was not declared in this scope
  175 |         arb[poz1].mx = max(val, arb[poz2].mx);
      |         ^~~
a.cc:186:9: error: 'arb' was not declared in this scope
  186 |         arb[poz1].st = upd(arb[poz2].st , st, mid, a, val);
      |         ^~~
a.cc:193:9: error: 'arb' was not declared in this scope
  193 |         arb[poz1].dr = upd(arb[poz2].dr , mid + 1, dr, a, val);
      |         ^~~
a.cc:198:5: error: 'arb' was not declared in this scope
  198 |     arb[poz1].mx = max({arb[arb[poz1].st].mx, arb[arb[poz1].dr].mx, arb[arb[poz2].st].mx, arb[arb[poz2].dr].mx});
      |     ^~~
a.cc:198:23: error: no matching function for call to 'max(<brace-enclosed initializer list>)'
  198 |     arb[poz1].mx = max({arb[arb[poz1].st].mx, arb[arb[poz1].dr].mx, arb[arb[poz2].st].mx, arb[arb[poz2].dr].mx});
      |                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 1 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   candidate expects 2 arguments, 1 provided
a.cc: At global scope:
a.cc:203:8: error: 'MAX_N' was not declared in this scope
  203 | int rz[MAX_N + 1];
      |        ^~~~~
a.cc: In function 'void solve()':
a.cc:209:5: error: reference to 'cout' is ambiguous
  209 |     cout << "1\n";
      |     ^~~~
/usr/include/c++/14/iostream:63:18: note: candidates are: 'std::ostream std::cout'
   63 |   extern ostream cout;          ///< Linked to standard output
      |                  ^~~~
a.cc:17:10: note:                 'std::ofstream cout'
   17 | ofstream cout("out.txt");
      |          ^~~~
a.cc:211:11: error: 'root' was not declared in this scope
  211 |     aloca(root[1]);
      |           ^~~~
a.cc:215:26: error: 'v' was not declared in this scope
  215 |     build(root[1], 1, n, v[1], 1);
      |                          ^
a.cc:219:17: error: 'dfn' was not declared in this scope; did you mean 'dfs'?
  219 |         int i = dfn[j];
      |                 ^~~
      |                 dfs
a.cc:221:31: error: 'tata' was not declared in this scope
  221 |         int rez = getMax(root[tata[i]], 1, n, 1, v[i] - 1) + 1;
      |                               ^~~~
a.cc:224:9: error: 'rz' was not declared in this scope; did you mean 'rez'?
  224 |         rz[i] = max(rez, rz[tata[i]]);
      |         ^~
      |         rez
a.cc:228:9: error: reference to 'cout' is ambiguous
  228 |         cout << rz[i] << "\n";
      |         ^~~~
/usr/include/c++/14/iostream:63:18: note: candidates are: 'std::ostream std::cout'
   63 |   extern ostream cout;          ///< Linked to standard output
      |                  ^~~~
a.cc:17:10: note:                 'std::ofstream cout'
   17 | ofstream cout("out.txt");
      |          ^~~~
a.cc:228:17: error: 'rz' was not declared in this scope
  228 |         cout << rz[i] << "\n";
      |                 ^~