Time Limit: 7000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 409 Accepted Submission(s): 109
#include <bits/stdc++.h> using namespace std; const int maxn = 6e5 + 10; int n; int val[maxn], dfn[maxn], l[maxn], r[maxn], tot, cnt, nx[maxn], to[maxn], c[maxn], vis[maxn]; vector<int> G[maxn]; struct node { int L, R, pos; bool operator<(const node &cur) const { if (L == cur.L)return R < cur.R; return L < cur.L; } } o[maxn]; inline void dfs(int cur, int f) { l[cur] = ++tot; dfn[tot] = val[cur]; for (register int i = 0; i < G[cur].size(); ++i) { int to = G[cur][i]; if (to == f)continue; dfs(to, cur); } r[cur] = tot; } inline int lowbit(int x) { return x & (-x); } inline void update(int pos, int val) { while (pos <= n) { c[pos] += val; pos += lowbit(pos); } } inline int query(int pos) { int res = 0; while (pos) { res += c[pos]; pos -= lowbit(pos); } return res; } int q[maxn]; int main() { #ifndef ONLINE_JUDGE freopen("1.txt", "r", stdin); #endif while (scanf("%d", &n) != EOF) { tot = 0; memset(q, 0, sizeof(q)); for (register int i = 1; i <= n; ++i) { G[i].clear(); } for (register int i = 2, pi; i <= n; ++i) { scanf("%d", &pi); G[pi].emplace_back(i); G[i].emplace_back(pi); } int mx = -1; for (register int i = 1; i <= n; ++i) { scanf("%d", &val[i]); mx = max(mx, val[i]); } dfs(1, -1); cnt = 0; for (register int i = 0; i <= mx; ++i) { to[i] = 2 * n + 1; vis[i] = 0; } for (register int i = 1; i <= n; ++i) { dfn[i + n] = dfn[i]; o[++cnt] = node{l[i], r[i], i}; o[++cnt] = node{r[i] + 1, l[i] - 1 + n, i}; } sort(o + 1, o + 1 + cnt); n *= 2; for (register int i = n; i >= 1; --i) { nx[i] = to[dfn[i]]; to[dfn[i]] = i; c[i] = 0; } for (register int i = 1; i <= n; ++i) { if (!vis[dfn[i]]) { vis[dfn[i]] = 1; update(i, 1); } } int Left = 1, res = 0; for (register int i = 1; i <= cnt; ++i) { while (Left < o[i].L) { if (nx[Left] <= n)update(nx[Left], 1); ++Left; } q[o[i].pos] += query(o[i].R) - query(o[i].L - 1); res = max(res, q[o[i].pos]); } printf("%d\n", res); } return 0; }
原文:https://www.cnblogs.com/czy-power/p/11433485.html