This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e6+5;
const ll inf=2e18;
ll n,a[maxN+1],dp[maxN+1][2];
vector<ll> adj[maxN+1],vec[maxN+1];
void dfs(ll u,ll p)
{
for(auto v:adj[u])
{
if(v!=p)
{
vec[u].push_back(v);
}
}
vector<vector<ll>> f(vec[u].size()+1,vector<ll>(2));
for(int i=0;i<=vec[u].size();i++)
{
f[i][0]=f[i][1]=-inf;
}
f[0][0]=f[0][1]=(a[u]==1);
ll mx=0;
for(int i=0;i<vec[u].size();i++)
{
ll v=vec[u][i];
dfs(v,u);
if(a[u]!=1)
{
f[i+1][0]=f[i+1][1]=0;
}
else
{
f[i+1][0]=max(f[i][0],dp[v][0]+1);
f[i+1][1]=max(f[i][1],dp[v][0]+mx);
}
mx=max(mx,f[i+1][0]);
}
dp[u][0]=f[vec[u].size()][0];
dp[u][1]=f[vec[u].size()][1];
}
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ld mn=(ld)inf;
ll sl,val;
cin>>n;
for(int i=1;i<n;i++)
{
ll u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(mn>a[i])
{
mn=a[i];
val=a[i];
sl=1;
}
}
dfs(1,0);
for(int i=1;i<=n;i++)
{
ld cur=(ld)1.0*max(dp[i][0],dp[i][1]);
if(cur==0)
{
continue;
}
ld tmp=(ld)1.0*1/cur;
//cout<<i<<" "<<cur<<'\n';
if(mn>tmp)
{
mn=tmp;
val=1;
sl=max(dp[i][0],dp[i][1]);
}
}
cout<<val<<"/"<<sl;
}
Compilation message (stderr)
mag.cpp: In function 'void dfs(long long int, long long int)':
mag.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0;i<=vec[u].size();i++)
| ~^~~~~~~~~~~~~~~
mag.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i=0;i<vec[u].size();i++)
| ~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |