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 fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair< int, int > ii;
const int N = 1e6 + 5;
const long long infll = (long long)(1e18);
int n, f[N][2], x[N], pref[2];
vector< int > graph[N];
bool vis[N];
double mn;
long long X, Y;
double F(long long a, long long b) {
if( b == 0 ) return infll;
else return (double)( (double)( a ) / (double)( b ) );
}
void dfs(int u, int p) {
f[u][ x[u] - 1 ] = 1;
vis[u] = 1;
for(int i = 0; i < (int)( graph[u].size() ); i++ ) {
int v = graph[u][i];
if( v == p || x[v] > 2 ) continue;
dfs( v, u );
if( x[u] == 1 ) {
f[u][0] = max( f[u][0], f[v][0] + 1 );
f[u][1] = max( f[u][1], f[v][1] + 1 );
}
else
f[u][1] = max( f[u][1], f[v][0] + 1 );
}
pref[0] = pref[1] = 0;
for(int i = 0; i < (int)( graph[u].size() ); i++ ) {
int v = graph[u][i];
if( v == p || x[v] > 2 ) continue;
if( x[u] == 1 ) {
if( f[v][0] && F( 1, f[v][0] + 1 + pref[0] ) < mn ) {
X = 1;
mn = F( 1, f[v][0] + 1 + pref[0] );
Y = f[v][0] + 1 + pref[0];
}
if( f[v][1] && F( 2, f[v][1] + 1 + pref[0] ) < mn ) {
X = 2;
mn = F( 2, f[v][1] + 1 + pref[0] );
Y = f[v][1] + 1 + pref[0];
}
if( f[v][0] && F( 2, f[v][0] + 1 + pref[1] ) < mn ) {
X = 2;
mn = F( 2, f[v][0] + 1 + pref[1] );
Y = f[v][0] + 1 + pref[1];
}
}
else {
if( f[v][0] && F( 2, f[v][0] + 1 + pref[0] ) < mn ) {
X = 2;
mn = F( 2, f[v][0] + 1 + pref[0] );
Y = f[v][0] + 1 + pref[0];
}
}
for(int j = 0; j < 2; j++)
pref[j] = max( pref[j], f[v][j] );
}
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
graph[u].pb(v);
graph[v].pb(u);
}
mn = infll;
for(int i = 1; i <= n; i++) {
cin >> x[i];
if(x[i] < mn) {
mn = x[i];
X = x[i];
Y = 1;
}
}
for(int i = 1; i <= n; i++) {
if(!vis[i] && x[i] < 3) {
dfs( i, i );
}
}
for(int i = 1; i <= n; i++) {
if(!vis[i]) continue;
if( F( 1, f[i][0] ) < mn ) {
X = 1;
mn = F( 1, f[i][0] );
Y = f[i][0];
}
if( F( 2, f[i][1] ) < mn ) {
X = 2;
mn = F( 2, f[i][1] );
Y = f[i][1];
}
}
cout << X << "/" << Y;
}
# | 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... |