HDU 6409 沒有兄弟的舞會

#include<bits/stdc++.h>
using namespace std;

#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
typedef long long LL;
const int maxn=100000+100;

struct Edge{
    
    int to,next;
}edge[maxn];
int head[maxn],tot;

int ans[maxn],amax[maxn],bmax[maxn],amin[maxn],bmin[maxn],Max,Min;
LL MAX,MIN;
int fa[maxn];

inline void DFS(int u){
    
    amax[u]=bmax[u]=0;
    amin[u]=bmin[u]=0;
    for(int i=head[u];i!=-1;i=edge[i].next){
        
        Edge e=edge[i];
        int v=e.to;
        DFS(v);
        bmax[u]=max(bmax[u],ans[v]);
        if(bmax[u]>amax[u]) swap(amax[u],bmax[u]);
        bmin[u]=min(bmin[u],ans[v]);
        if(bmin[u]<amin[u]) swap(amin[u],bmin[u]);
    }
    if(head[u]!=-1){
        
        MAX+=amax[u];
        MIN+=amin[u];
        Max=max(Max,bmax[u]);
        Min=min(Min,bmin[u]); 
    }
}

int main(){
    
    int T;
    scanf("%d",&T);
    while(T--){
        
        int n;
        scanf("%d",&n);
        for(int i=2;i<=n;i++) scanf("%d",&fa[i]);
        for(int i=1;i<=n;i++) scanf("%d",&ans[i]),head[i]=-1;
        tot=0;
        for(int i=2;i<=n;i++){
            
            edge[tot].to=i;
            edge[tot].next=head[fa[i]];
            head[fa[i]]=tot++;
        }
        MAX=MIN=0;
        Max=Min=0;
        DFS(1);
        MAX=max(MAX,MAX+Max);
        MIN=min(MIN,MIN+Min);
        if(ans[1]>0) MAX+=ans[1];
        else MIN+=ans[1];
        printf("%lld %lld\n",MAX,MIN);
    }
}