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

The city consists of 𝑛 squares connected by 𝑛−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 𝑎𝑖 citizens on the 𝑖-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 𝑛 — the number of squares in the city (2≤𝑛≤2⋅105).

The second line contains 𝑛−1 integers 𝑝2,𝑝3…𝑝𝑛 meaning that there is a one-way road from the square 𝑝𝑖 to the square 𝑖 (1≤𝑝𝑖<𝑖).

The third line contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 — the number of citizens on each square initially (0≤𝑎𝑖≤109).

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

Examples
input

3
1 1
3 1 2

output

input

3
1 1
3 1 3

output

Note
In the first example the citizens on the square 1 can split into two groups 2+1, so that the second and on the third squares will have 3 citizens each.

In the second example no matter how citizens act the bandit can catch at least 4 citizens.

题目大意

有一个有向边的树，树的根节点可以走到任意一个叶子节点。每个节点都有权值，现在每个节点都可以往孩子节点走，权值任意分配。问当所有权值都分布在了叶子节点，叶子节点的最大权值最小是多少？

解法

二分叶子节点的最大权值w，然后遍历每一个叶子节点，从它最近有值的父节点获取权值，所有节点获取权值后，不能超过w，当所以叶子节点都完成了从父节点获取权值后，看非叶子节点是否还有剩余权值，有的话就是方案不合法，否则合法。

为了加快叶子节点向父亲获取权值的效率，加入了并查集。也就是当一个节点的权值变成了0，那么其他叶子节点就无需遍历它，而应该直接走到在它之上有权值的节点。所以直接让权值为0的节点合并到其父亲节点，后续其父亲节点也可能会合并到父亲的父亲，所以使用并查集就压缩了路径。

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 2e5+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}


//--------------------------------------------
int N;
ll h[maxn],e[maxn],ne[maxn],p[maxn],idx = 1;
ll fa[maxn];
ll p2[maxn],fa2[maxn];
bool yz[maxn];
ll f[maxn];
void add(int a,int b){
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}
int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}
void dfs1(int u){
    int tg = 1;
    for(int i = h[u];i;i = ne[i]){
        int v = e[i];
        fa[v] = u;
        tg = 0;
        dfs1(v);
    }
    if(tg){
        yz[u] = 1;
    }
}

bool judge(ll mid){
    for(int i = 1;i<=N;i++) f[i] = i;
    for(int i = 1;i<=N;i++) fa2[i] = fa[i],p2[i] = p[i]; //拷贝

    for(int i = 1;i<=N;i++){
        if(!yz[i]) continue;
        int up = find(fa[i]);
        if(p2[i] > mid) return 0;
        while(p2[i] < mid && up != 0){
            ll ca = mid - p2[i];
            if(p2[up] > ca){
                p2[up] -= ca;
                p2[i] += ca;
            }else{
                p2[i] += p2[up];
                p2[up] = 0;
                f[find(up)] = fa[up];
                up = find(up);
            }
        }
    }
    for(int i = 1;i<=N;i++){
        if(!yz[i] && p2[i]>0) return 0;
    }
    return 1;
}
void solve(){
     ll l = 0,r = 1e17,ans;
     while(l<=r){
         ll mid = (l+r)>>1;
         if(judge(mid)) r = mid-1,ans = mid;
         else l = mid+1;
     }
     printf("%lld\n",ans);
}
int main(){
//    debug_in;

    read(N);
    for(int i = 2;i<=N;i++){
        int t;read(t);
        add(t,i);
    }
    for(int i = 1;i<=N;i++){
        read(p[i]);
        p2[i] = p[i];
    }
    dfs1(1);
    solve();

    return 0;
}

D. Bandit in a City 【树+并查集】1900

题目大意

解法

-----------