CF1436D

Bandits appeared in the city! One of them is trying to catch as many citizens as he can.

The city consists of n squares connected by $n−1$ roads in such a way that it is possible to reach any square from any other square. The square number 1 is the main square.

After Sunday walk all the roads were changed to one-way roads in such a way that it is possible to reach any square from the main square.

At the moment when the bandit appeared on the main square there were $ ai $ citizens on the i-th square. Now the following process will begin. First, each citizen that is currently on a square with some outgoing one-way roads chooses one of such roads and moves along it to another square. Then the bandit chooses one of the one-way roads outgoing from the square he is located and moves along it. The process is repeated until the bandit is located on a square with no outgoing roads. The bandit catches all the citizens on that square.

The bandit wants to catch as many citizens as possible; the citizens want to minimize the number of caught people. The bandit and the citizens know positions of all citizens at any time, the citizens can cooperate. If both sides act optimally, how many citizens will be caught?

Input

The first line contains a single integer n — the number of squares in the city $(2≤n≤2⋅10^5)$.

The second line contains $n−1$ integers $p2,p3…pn$ meaning that there is a one-way road from the square pi to the square $ i (1≤pi<i)$.

The third line contains n integers $a1,a2,…,an $— the number of citizens on each square initially $(0≤ai≤10^9)$.

Output

Print a single integer — the number of citizens the bandit will catch if both sides act optimally.

Examples

input

1
2
3
3
1 1
3 1 2

output

1
3

input

1
2
3
3
1 1
3 1 3

output

1
4

使最后叶子节点的最大值最小。

从根节点到子节点分流的时候可能使得结果变大，也可能不变

当 $d[u] * cnt[u] < sum[u]$ (三个值分别表示该子树最大值，子树叶子个数，子树所有节点之和)时，结果一定是要变大的, 否则是不变的。

因为是从根节点开始分流，从叶子节点往上更新就可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const ll INF=0x3f3f3f3f3f3f3f3f;
const int MAX=200000+10;
int a[MAX],n,x,fa[MAX],cnt[MAX];
ll sum[MAX],d[MAX];
bool vis[MAX];
int h[MAX],tot=0;
struct edge{
	int to,next;
}e[MAX*2];
void addedge(int u,int v){
	e[tot].to = v;
	e[tot].next = h[u];
	h[u] = tot++;
}
void dfs(int u){
	vis[u] = 1;
	d[u] = -INF;sum[u] = a[u];
	for(int i=h[u];i!=-1;i=e[i].next){
		int v = e[i].to;
		if(vis[v]) continue;
		dfs(v);
		cnt[u] += max(1,cnt[v]);
		sum[u] += sum[v];
		d[u] = max(d[u],d[v]);
	}
	if(d[u]==-INF) d[u] = a[u];
	else if(d[u] * cnt[u]<sum[u]) {
		d[u] = sum[u]/cnt[u];
		if(sum[u]%cnt[u]) d[u] += 1;
	}
}
int main(){
//	freopen("in","r",stdin);
	mem(h,-1);
	sf(n);
	fi(i,2,n+1) {
		sf(x);
		addedge(x,i);
	}
	fi(i,1,n+1) sf(a[i]); 
	dfs(1);
	printf("%lld",d[1]);
	return 0;
}