#include #include #include #include #include #include using namespace std; templatebool chmax(T& xx, T yy) { if (xx < yy) { xx = yy; return true; }return false; } template class dynamic_lazysegtree { struct node { S sum; F lazy; node* child[2]; node() { sum = e(); lazy = id(); child[0] = nullptr; child[1] = nullptr; } }; node* root = new node(); int limit, depth, queryl = 0, queryr = 0; S scopy; F fcopy; S getsum(node* np) { return np ? np->sum : e(); } void eval(node*& np, bool bo) { if (np->lazy == id())return; if (bo) { //子に伝播 if (!np->child[0]) np->child[0] = new node(); np->child[0]->lazy = composition(np->lazy, np->child[0]->lazy); if (!np->child[1])np->child[1] = new node(); np->child[1]->lazy = composition(np->lazy, np->child[1]->lazy); } np->sum = mapping(np->lazy, np->sum); np->lazy = id(); } void set(node*& np, int pos, int dep) { if (!np) np = new node(); eval(np, dep >= 0); if (dep == -1) { np->sum = scopy; return; } set(np->child[(bool)(pos & (1 << dep))], pos, dep - 1); np->sum = op(getsum(np->child[0]), getsum(np->child[1])); return; } void apply(node*& np, int l, int r) { if (!np)np = new node(); eval(np, r - l > 1); if (queryl <= l && r <= queryr) { np->lazy = composition(fcopy, np->lazy); eval(np, r - l > 1); } else if (queryl < r && l < queryr) { apply(np->child[0], l, (l + r) / 2); apply(np->child[1], (l + r) / 2, r); np->sum = op(getsum(np->child[0]), getsum(np->child[1])); } } S prod(node* np, int l, int r) { if (r <= queryl || queryr <= l || !np) { return e(); } eval(np, r - l > 1); if (queryl <= l && r <= queryr) { return np->sum; } else { return op(prod(np->child[0], l, (l + r) / 2), prod(np->child[1], (l + r) / 2, r)); } } public: dynamic_lazysegtree(int N) { assert(0 < N); depth = 0; while ((1U << depth) < (unsigned int)(N)) depth++; limit = 1 << depth; } void set(int pos, S x) { assert(0 <= pos && pos < limit); scopy = x; set(root, pos, depth - 1); } S get(int pos) { assert(0 <= pos && pos < limit); node* np = root; for (int i = depth - 1; i >= 0; i--) { eval(np, true); np = np->child[(bool)(pos & (1 << i))]; if (!np)return e(); } eval(np, false); return np->sum; } void apply(int l, int r, F x) { assert(0 <= l && l <= r && r <= limit); if (l == r)return; queryl = l; queryr = r; fcopy = x; apply(root, 0, limit); } S prod(int l, int r) { assert(0 <= l && l <= r && r <= limit); if (l == r)return e(); queryl = l; queryr = r; return prod(root, 0, limit); } S all_prod() { eval(root, true); return root->sum; } }; long long op(long long x, long long y) { return max(x, y); } long long e() { return 0; } long long mapping(pair f, long long x) { if (f.second == -1) return x + f.first; return f.second; } pair composition(pair f1, pair f2) { if (f1.second != -1) return make_pair(0, f1.second); if (f2.second == -1) return make_pair(f2.first + f1.first, -1); return make_pair(0, f2.second + f1.first); } pair id() { return make_pair(0, -1); } //加算 代入 using mysegtree = dynamic_lazysegtree, mapping, composition, id>; int N; vector>tree; //木グラフ vector>numbers; //木の頂点に乗っている数 vector>elements; //頂点iより下の部分木にある要素 vector dp; //dpテーブル //dp[i][j]=i番目のノードで下限がjのとき、そのノードより下の部分木で最高得点 void dfs(int x) { for (int i = 0; i < tree[x].size(); i++) { dfs(tree[x][i]); } int a = -1/*子部分木の中で頂点数が最大の物のindex*/, b = -1/* elememts[a].size()*/; for (int i = 0; i < tree[x].size(); i++) { if (chmax(b, (int)elements[tree[x][i]].size())) a = i; } if (a != -1) { swap(dp[x], dp[tree[x][a]]); swap(elements[x], elements[tree[x][a]]); } for (int i = 0; i < tree[x].size(); i++) { if (i == a)continue; long long m = 0; for (auto itr = elements[tree[x][i]].rbegin(); itr != elements[tree[x][i]].rend(); ) { chmax(m, dp[tree[x][i]].get(*itr)); int r = *itr + 1, l = (++itr == elements[tree[x][i]].rend() ? 0 : *itr + 1); dp[x].apply(l, r, make_pair(m, -1)); } elements[x].merge(elements[tree[x][i]]); } int pos = numbers[x].first - 1, l = 0, r = pos + 1, update = dp[x].prod(pos, N) + numbers[x].second; while (r - l > 1) { int mid = (l + r) / 2; if (dp[x].get(mid - 1) < update) r = mid; else l = mid; } dp[x].apply(l, pos + 1, make_pair(0, update)); elements[x].insert(pos); } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> N; tree.resize(N); numbers.resize(N); elements.resize(N); int a; for (int i = 1; i < N; i++) { //木の構築 cin >> a; tree[a - 1].push_back(i); } for (int i = 0; i < N; i++) { //入力 cin >> a; numbers[i].first = a; } for (int i = 0; i < N; i++) { //入力 cin >> a; numbers[i].second = a; } dp.resize(N, mysegtree(N)); for (int i = 0; i < N; i++)dp[i] = mysegtree(N); dfs(0); cout << dp[0].all_prod() << endl; }