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) {
__int128 mcm = (a.den*b.den)/__gcd(a.den,b.den);
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];
fract def[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));
}
}
void calc(ll nd){
def[nd] = down[nd];
if(parent[nd] != -1){
def[nd] = min(def[nd],fract(magic[parent[nd]]*def[nd].num,def[nd].den+1));
for(auto i:adj[parent[nd]]){
if(i==nd) continue;
def[nd] = min( def[nd] , fract(def[nd].num*magic[parent[nd]]*down[i].num, def[nd].den+down[i].den+1));
}
}
for(auto i:adj[nd]) calc(i);
}
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);
/*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';*/
calc(root);
fract res=def[root];
forn(i,0,n){ res=min(res,def[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... |