树上前缀和，dfn序，改树为链

牛客周赛88 G

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
const int N=2e5+10;
#define int long long
int a[N],f[N],w[N];
int n,q;
int pre[N];
int L[N],R[N];
map<int,int >mp;
int pre_mx[N],suf_mx[N];
vector<int> leaf(1,0);
vector<int> adj[N];
void add(int x,int y){
    w[y]=max(w[y],a[y]+w[x]);
    if(f[y]==0) return;
    add(y,f[y]);
}
void del(int x,int y){
    w[y]=a[y];
    for(auto v:adj[y]){
        if(v==x) continue;
        w[y]=max(w[y],w[v]+a[y]);
    }
    if(f[y]==0) return;
    del(x,f[y]);
}
void dfs(int u,int fa){
    w[u]=a[u];
    pre[u]=pre[fa]+a[u];
    L[u]=R[u]=u;
    if(adj[u].size()==0){
        mp[u]=leaf.size();
        leaf.push_back(u);
        return;
    }
    for(auto v:adj[u]){
        if(v==fa) continue;
        dfs(v,u);
        w[u]=max(w[u],w[v]+a[u]);
    }
    L[u]=L[adj[u][0]];
    R[u]=R[adj[u][adj[u].size()-1]];
}
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        w[i]=a[i];
    }
    for(int i=2;i<=n;i++){
        cin>>f[i];
        adj[f[i]].push_back(i);
    }
    dfs(1,0);
    for(int i=1;i<leaf.size();i++){
        pre_mx[i]=max(pre_mx[i-1],pre[leaf[i]]);
    }
    for(int i=leaf.size()-1;i>=1;i--){
        suf_mx[i]=max(suf_mx[i+1],pre[leaf[i]]);
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        int l=mp[L[x]],r=mp[R[x]];
        int ans=max(pre_mx[l-1],suf_mx[r+1]);
        ans=max(ans,pre[f[x]]);
        ans=max(ans,pre[y]+w[x]);
        cout<<ans<<endl;
    }
    return 0;
}