This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
Code by @marlov
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
#define maxN 1000005
#define INF (ll)1000000001
ll N;
vector<ll> adj[maxN];
ll magic[maxN];
pair<ll,ll> dp[maxN];
pair<ll,ll> dp2[maxN];
ll top=INF;
ll bottom=1;
ll GCD(ll a,ll b){
if(a==0) return b;
return GCD(b%a,a);
}
void ps(ll t1,int b1){
if(top*b1>t1*bottom){
top=t1;
bottom=b1;
}
}
void dfs(int n,int p){
for(int i:adj[n]) if(i!=p){
dfs(i,n);
}
//go through all children and try to connect\
//if magic greater than 2 return
if(magic[n]>2) return;
for(int i:adj[n]) if(i!=p){
//possible route through that node
ps(dp[n].first*dp[i].first,dp[n].second+dp[i].second);
if(magic[n]==1){
if(dp[n].first*dp[i].second>dp[i].first*dp[n].second){
dp[n].first=dp[i].first;
dp[n].second=dp[i].second+1;
}
if(dp2[n].first*dp2[i].second>=dp2[i].first*dp2[n].second){
dp2[n].first=2;
dp2[n].second=dp2[i].second+1;
}
}else if(magic[n]==2){
if(dp[i].second>=dp2[n].second){
dp2[n].first=2;
dp2[i].second=dp[i].second+1;
}
}
}
ps(dp2[n].first,dp2[n].second);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N;
ll u,v;
for(int i=0;i<N-1;i++){
cin>>u>>v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=0;i<N;i++){
cin>>magic[i];
top=min(magic[i],top);
dp[i].first=magic[i];
dp[i].second=1;
dp2[i].first=INF;
dp2[i].second=1;
}
//
dfs(0,-1);
/*
for(int i=0;i<N;i++){
cout<<i+1<<" has "<<dp[i].first<<" and "<<dp[i].second<<'\n';
}
*/
cout<<top/GCD(top,bottom)<<"/"<<bottom/GCD(top,bottom)<<'\n';
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1,n=0?)
* do smth instead of nothing and stay organized
*/
Compilation message (stderr)
mag.cpp:53:2: warning: multi-line comment [-Wcomment]
53 | //go through all children and try to connect\
| ^
# | 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... |