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 pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
typedef long long ll;
const int MAXN = 1000000+5;
struct fract{
__int128 num;
__int128 den;
fract(__int128 num = 1, __int128 den = 1) : num(num) , den(den) {}
};
bool operator<(const fract &a, const fract &b) {
//cout << to_string((ll)a.num)<<"/"<<to_string((ll)a.den) << " ";
//cout << to_string((ll)b.num)<<"/"<<to_string((ll)b.den) << " ";
__int128 mcm = (a.den*b.den)/__gcd(a.den,b.den);
//cout<<ll(a.num*(mcm/a.num))<<" "<< ll(b.num*(mcm/b.den))<<'\n';
return (a.num*(mcm/a.den)) < (b.num*(mcm/b.den));
}
ll n;
vector<ll> adj[MAXN];
ll parent[MAXN];
ll magic[MAXN];
fract down[MAXN];
void downcalc(ll nd){
down[nd].num=magic[nd];
down[nd].den=1;
for(auto i:adj[nd]){
downcalc(i);
down[nd] = min(down[nd],fract(down[nd].num*down[i].num,down[nd].den+down[i].den));
}
}
int main(){
mset(parent,-1);
cin>>n;
ll a,b;
forn(i,0,n-1){
cin>>a>>b; a--; b--;
adj[a].pb(b);
parent[b]=a;
}
forn(i,0,n) cin>>magic[i];
ll root = 0;
forn(i,0,n) if(parent[i] == -1) root = i;
downcalc(root);
//forn(i,0,n) cout << to_string((ll)down[i].num)<<"/"<<to_string((ll)down[i].den) << '\n';
fract res=down[root];
forn(i,0,n){ res=min(res,down[i]);}
cout<<to_string((ll)res.num)<<"/"<<to_string((ll)res.den)<<'\n';
return 0;
}
# | 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... |