#include<bits/stdc++.h>
using namespace std;
ifstream fin("milkvisits.in");
ofstream fout("milkvisits.out");
#define NMAX 1000005
typedef long long ll;
vector<int> v[NMAX];
ll val[NMAX];
ll P[NMAX];
ll minim = (1<<30);
ll dfs(int nod,int tata)
{
val[nod] = P[nod];
for(auto u : v[nod])
{
if(u != tata)
{
dfs(u,nod);
val[nod] += val[u];
}
}
}
void dfs2(int nod,int tata)
{
ll maxim = val[0] - val[nod];
for(auto u : v[nod])
{
if(u != tata)
{
maxim = max(maxim,val[u]);
}
}
//cout<<nod<<" "<<maxim<<endl;
minim = min(minim,maxim);
for(auto u : v[nod])
{
if(u != tata)
{
dfs2(u,nod);
}
}
}
int LocateCentre(int n,ll p[],ll s[],ll d[])
{
for(int i=0;i<=n-2;i++)
{
int a = s[i];
int b = d[i];
v[a].push_back(b);
v[b].push_back(a);
}
for(int i=0;i<=n-1;i++)
P[i] = p[i];
dfs(0,-1);
dfs2(0,-1);
return minim;
}
/*
int main()
{
ll p[NMAX],s[NMAX],d[NMAX];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>p[i];
}
for(int i=0;i<=n-2;i++)
{
int a,b;
cin>>s[i]>>d[i];
}
cout<<LocateCentre(n,p,s,d);
}
5
10 10 10 20 20
0 2
1 2
2 3
3 4
*/
Compilation message
traffic.cpp: In function 'll dfs(int, int)':
traffic.cpp:26:1: warning: no return statement in function returning non-void [-Wreturn-type]
26 | }
| ^
/tmp/ccPluOZ3.o: In function `main':
grader.cpp:(.text.startup+0xd9): undefined reference to `LocateCentre(int, int*, int*, int*)'
collect2: error: ld returned 1 exit status
