记录每个节点的树上前缀和(pref)以及以该节点为根节点到叶子节点的最大权值和(dp),x被放到y的结点下面,那么以x为根节点的子树就废了,把pref[y]加上dp[x],并且忽略这棵子树,可以通过前序遍历的编号来确定子树的范围,通过线段树来维护前缀值
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define len(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define db(x) cerr << #x << "=" << (x) << " "
#define el cerr << "\n"
const int MN=2e5;
vector<int> adj[MN+5];
ll pref[MN+5], dp[MN+5], a[MN+5];
int siz[MN+5], dfn[MN+5], id;
template<class Info>
class SegmentTree {
private:
int n;
vector<Info> info, a;
public:
SegmentTree(int n) {
this->n=n;
info.resize(4*n+1);
this->a=a;
build(1, 1, n);
}
void build(int id, int l, int r) {
if (l==r) {
info[id]=Info();
return;
}
int mid=(l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
info[id]=info[id*2]+info[id*2+1];
}
void modify(int id, int l, int r, int p, const Info& v) {
if (l==r) {
info[id]=v;
return;
}
int mid=(l+r)/2;
if (p<=mid)
modify(id*2, l, mid, p, v);
else
modify(id*2+1, mid+1, r, p, v);
info[id]=info[id*2]+info[id*2+1];
}
void modify(int p, const Info& v) {
p++;
modify(1, 1, n, p, v);
}
Info query(int id, int l, int r, int s, int e) {
if (s<=l && e>=r) {
return info[id];
}
if (r<s || l>e) {
return Info();
}
int mid=(l+r)/2;
return query(id*2, l, mid, s, e)+query(id*2+1, mid+1, r, s, e);
}
Info query(int l, int r) {
l++, r++;
return query(1, 1, n, l, r);
}
};
class Info {
public:
ll x;
Info() {
this->x=0;
}
Info(ll x) {
this->x=x;
}
};
Info operator+(const Info& a, const Info& b) {
Info c;
c.x=max(a.x, b.x);
return c;
}
void dfs(int u, int p) {
dfn[u]=++id;
dp[u]=a[u];
siz[u]=1;
pref[u]=pref[p]+a[u];
ll mx=0;
for (int v : adj[u]) {
if (v==p)
continue;
dfs(v, u);
siz[u]+=siz[v];
mx=max(mx, dp[v]);
}
dp[u]+=mx;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> p(n+1);
for (int i=1; i<=n; i++) {
cin >> a[i];
}
for (int i=2; i<=n; i++) {
cin >> p[i];
adj[p[i]].push_back(i);
adj[i].push_back(p[i]);
}
dfs(1, 0);
SegmentTree<Info> seg(n+1);
for (int i=1; i<=n; i++) {
seg.modify(dfn[i], pref[i]);
}
while (q--) {
int x, y;
cin >> x >> y;
Info oldv=seg.query(dfn[y], dfn[y]);
Info newv=oldv;
newv.x+=dp[x];
seg.modify(dfn[y], newv);
int l=dfn[x];
int r=l+siz[x]-1;
ll ans=seg.query(1, l-1).x;
ans=max(ans, seg.query(r+1, n).x);
cout << ans << "\n";
seg.modify(dfn[y], oldv);
}
return 0;
}