# 題目
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]; | |
} |