# 題目

AP325 Q-8-6. 樹狀圖的距離總和

# 解題思路

目前沒東西...

# 程式碼

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n,w[N],num[N]={0};
long long total=0,dis_son[N]={0},dis[N]={0};
vector<int> child[N];
void dfs(int p){//O(n)
    for(auto e:child[p]){
        int u=e;
        dfs(u);
        dis_son[p]+=dis_son[u]+num[u]*w[u];
        num[p]+=num[u];
    }
    num[p]++;
}
void dfs_dis(int p){//O(n)
    for(auto e:child[p]){
        int u=e;
        dis[u]=dis[p]-(dis_son[u]+num[u]*w[u])+(n-num[u])*w[u]+dis_son[u];
        total+=dis[u];
        dfs_dis(e);
    }
}
queue<int> q;
void bfs_dis(){// 算總和的時候 bfs 程式碼
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(auto t:child[p]){
            int u=t;
            q.push(u);
            dis[u]=dis[p]-(dis_son[u]+num[u]*w[u])+(n-num[u])*w[u]+dis_son[u];
            total+=dis[u];
        }
    }
}
int main(){
    cin>>n;
    for(int i=2,temp;i<=n;i++){
        cin>>temp;
        child[temp].push_back(i);
    }
    for(int i=2;i<=n;i++)
        cin>>w[i];
    dfs(1);
    dis[1]=dis_son[1];
    dfs_dis(1);
    // q.push(1);
    // bfs_dis();
    cout<<total+dis_son[1];
}