1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| #include <bits/stdc++.h> #define mid ((l + r) >> 1) #define LL long long #define debug using namespace std;
const int N = 2e6+66, inf = 1e9+7;
vector<int>e[N]; int a[N], cnt, res; int head[N], rt[N << 2][6];
struct yhm{int ls, rs, sum;} tr[N << 2];
inline void insert(int &o, int l, int r, int p, int w) { if (! o) o = ++ cnt; tr[o].sum = max(tr[o].sum, w); if (l == r) return; if (p <= mid) insert(tr[o].ls, l, mid, p, w); if (p > mid) insert(tr[o].rs, mid + 1, r, p, w); }
inline int query(int o, int l, int r, int x, int y) { int sum(0); if (! o) return 0; if (l >= x && r <= y) return tr[o].sum; if (x <= mid) sum = max(sum, query(tr[o].ls, l, mid, x, y)); if (y > mid) sum = max(sum, query(tr[o].rs, mid + 1, r, x, y)); return sum; }
inline void merge(int &l, int r) { if (! l) {l = r; return;} if (! r) return; tr[l].sum = max (tr[l].sum, tr[r].sum); merge (tr[l].ls, tr[r].ls), merge (tr[l].rs, tr[r].rs); }
inline void dfs(int x) { int dododo(0), kakaka(0), i, y; insert (rt[x][0], 0, inf, a[x], 1); insert (rt[x][1], 0, inf, a[x], 1); for (i = 0; i < e[x].size(); ++ i) { y = e[x][i]; dfs(y); dododo = max (dododo, query (rt[y][0], 0, inf, 0, a[x] - 1)); kakaka = max (kakaka, query (rt[y][1], 0, inf, a[x] + 1, inf)); merge (rt[x][0], rt[y][0]); merge (rt[x][1], rt[y][1]); } insert (rt[x][0], 0, inf, a[x], dododo + 1); insert (rt[x][1], 0, inf, a[x], kakaka + 1); res = max (res, dododo + kakaka + 1); }
inline int thestars() { int i, n, fx; scanf ("%d", &n); for (i = 1; i <= n; ++ i) { scanf ("%d%d", &a[i], &fx); if (fx) e[fx].push_back(i); } dfs(1); cout << res; return 0; }
int youngore = thestars();
signed main() {;}
|