Submission #537256

#TimeUsernameProblemLanguageResultExecution timeMemory
537256ali22413836Mag (COCI16_mag)C++14
120 / 120
398 ms158604 KiB
#include <bits/stdc++.h>
#define  endl "\n"
using namespace std ;
typedef long long ll;
typedef long double ld ;
const int N=2e7;
const ll inf=1e18 ;
const ll mod = 1e9 + 7 ;
ll mypower(ll x, ll y){
    if(y == 0) return 1 ;
    if(y == 1) return x ;
    ll ret = mypower(x , y / 2);
    ret = (ret * ret) % mod;
    if(y % 2) ret = ( ret * x ) % mod ;
    return ret ;
}
ll dp1[1000006] , dp2[1000006] , n , a[1000006] ;
vector < ll > v[1000006] ;
void update(ll node , ll x){
    dp2[node] = max(dp2[node] , x) ;
    if(dp1[node] < dp2[node]){
        swap(dp1[node] , dp2[node]) ;
    }
    return ;
}
void dfs(ll node, ll par){
    for (auto p : v[node]){
        if (p == par) continue;
        dfs(p , node);
        if (a[p] == 1) update(node, dp1[p] + 1);
    }
}
void dfs1(ll node , ll par){
    for (auto p : v[node]){
        if (p == par) continue;
        if (a[node] == 1){
            if ((dp1[p] + 1) == dp1[node]) update(p , dp2[node] + 1) ;
            else update(p, dp1[node] + 1) ;
        }
        dfs1(p , node) ;
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n ;
    for(int i = 1 ; i < n ; i ++){
        ll x , y ;
        cin >> x >> y ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i] ;
    }
    dfs(1 , 1) ;
    dfs1(1  ,1) ;
    pair < ll , ll > ans = {1e18 , 1} ;
    for(int i = 1 ; i <= n;  i++){
        if(a[i] * ans.second < ans.first *(dp1[i] + dp2[i] + 1))
            ans = {a[i] , dp1[i] + dp2[i] + 1} ;
    }
    ll q = __gcd(ans.first , ans.second) ;
    ans.first /= q ;
    ans.second /= q ;
    cout << ans.first << "/" << ans.second << endl ;
    return 0 ;
}
		
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...