Time limit exceeded on test 4.

复杂度应该是 $O(\sum n)$ 啊。

#include<bits/stdc++.h>
// #define int long long
using namespace std;
typedef long long ll;
const int MAXN=2e5+5,mod=998244353;
const ll inf=1e9+1;
int T,n;
ll a[MAXN],f[MAXN],ans,maxn[MAXN],minn[MAXN],fa[MAXN];
ll read(){
    ll reans=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))reans=(reans<<1)+(reans<<3)+(ch^48),ch=getchar();
    return reans;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)return (void)putchar(x+48);
    write(x/10);
    putchar(x%10+48);
}
#define toi (e[i].to)
// #define roi (e[i^1].to)
#define fore(now,i) for(int i=head[now];i;i=e[i].next)
int cnt,head[MAXN];
struct EDGE{
    int to,next;
}e[MAXN<<1|1];
inline void addedge(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
vector<int> dps[MAXN];
void init(){
    cnt=ans=0;
    a[1]=f[0]=f[1]=fa[0]=fa[1]=0;
    maxn[0]=maxn[1]=-inf;
    minn[0]=minn[1]=inf;
    dps[1].clear();
}
void dfs0(int now,int p,int dp){
    maxn[dp]=max(maxn[dp],a[now]);
    minn[dp]=min(minn[dp],a[now]);
    fa[now]=p;
    dps[dp].push_back(now);
    fore(now,i)
        if(toi!=p)
            dfs0(toi,now,dp+1);
}
queue<pair<int,int> > q;
void bfs(){
    q.push(make_pair(1,1));
    while(!q.empty()){
        int now=q.front().first,dp=q.front().second;
        q.pop();
        if(now!=1){
            f[now]=f[fa[now]]+max(a[now]-minn[dp],maxn[dp]-a[now]);
            ll max1=-inf,max2=-inf;
            for(auto i:dps[dp])
                if(i!=now){
                    max1=max(max1,f[fa[i]]-a[i]);
                    max2=max(max2,f[fa[i]]+a[i]);
                }
            f[now]=max(f[now],max(max1+a[now],max2-a[now]));
        }
        ans=max(ans,f[now]);
        fore(now,i)
            if(toi!=fa[now])
                q.push(make_pair(toi,dp+1));
    }
}
void solve(){
    init();
    n=read();
    for(int i=0;i<=n;i++)
        head[i]=e[i].to=e[i].next=e[i+n].to=e[i+n].next=0;
    for(int i=2,u;i<=n;i++){
        u=read();
        addedge(i,u);
        addedge(u,i);
    }
    for(int i=2;i<=n;i++){
        a[i]=read();
        dps[i].clear();
        f[i]=fa[i]=0;
        maxn[i]=-inf;
        minn[i]=inf;
    }
    dfs0(1,1,1);
    bfs();
    write(ans);
    putchar('\n');
}
signed main(){
    // cin.tie(nullptr)->sync_with_stdio(false);
    // scanf("%d",&T);
    T=read();
    while(T--)
        solve();
    return 0;
}