codeforces-#528-D

codeforces-#528-D

十月 30, 2020

D. Minimum Diameter Tree

  • 题意

给出一颗n个点n-1条边的树

现在已知它的边权和=s

要求重新给这些边分配边权(非负数)

求分配后所能得到最小的树的直径

  • 题解

首先注意到无论怎么分配边权

树的直径一定是从一个叶子结点到另一个叶子结点

所以最终求得的树的直径也一定从某两个叶子结点的简单路径中产生

因为树的直径是树中最长路 我们要让最长路最短

那么就需要将边权和平均分配到所有叶子结点直接连接的那条边上

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
#define P pair<ll,ll>
const int Max=2e5+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;

ll num[Max];
ll leaves[Max],sz[Max],maxn=0;
bool vis[Max];
vector<int>mp[Max];
void dfs(int now){
    sz[now]=num[now];
    if(mp[now].empty())leaves[now]=1;
    for(auto to:mp[now]){
        dfs(to);
        sz[now]+=sz[to];
        leaves[now]+=leaves[to];
    }
    ll di=sz[now]%leaves[now]?1:0;
    //cout<<sz[now]<<" "<<leaves[now]<<endl;
    maxn=max(maxn,sz[now]/leaves[now]+di);
}
int main(){
    Turnoff;
    int n;cin>>n;
    for(int i=2;i<=n;i++){
        int u,v=i;cin>>u;
        mp[u].push_back(v);
    }
    for(int i=1;i<=n;i++)cin>>num[i];
    dfs(1);
    cout<<maxn<<endl;
}