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

D. Bandit in a City

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

3

input

3
1 1
3 1 3

output

4

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;
}

-----------

全部评论

相关推荐

06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务