#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const int N = 1e6 + 10;
const int inf = 1e9 + 1;
vector<int> g[N];
int a[N], d[N], x[N], P, Q, d2[N];
void dfs2(int v, int p){
if(a[v] == 1)
d[v] = 1;
int mx1 = 0, mx2 = 0;
for(int j = 0; j < sz(g[v]); j++){
int u = g[v][j];
if(u == p)
continue;
dfs2(u, v);
if(a[u] != 1)
continue;
d[v] = max(d[v], d[u] + (a[v] == 1));
if(d[u] > mx1){
mx2 = mx1;
mx1 = d[u];
}
else if(d[u] > mx2)
mx2 = d[u];
}
x[v] = max(mx1 + mx2 + (a[v] == 1), d[v]);
}
void dfs3(int v, int p){
int mx1 = -1, mx2 = -1, V = -1;
for(int j = 0; j < sz(g[v]); j++){
int u = g[v][j];
if(u == p)
continue;
if(a[u] == 1){
if(d[u] > mx1){
V = u;
mx2 = mx1;
mx1 = d[u];
}
else if(d[u] > mx2)
mx2 = d[u];
}
if(a[v] == 1)
d2[u] = max(d2[u], d2[v] + (a[v] == 1));
dfs3(u, v);
}
for(int j = 0; j < sz(g[v]); j++){
int u = g[v][j];
if(u == p)
continue;
int w = mx1;
if(u == V)
w = mx2;
if(a[v] == 1)
x[u] = max(x[u], w + (a[v] == 1) + d[u]);
}
x[v] = max(x[v], d2[v] + d[v]);
}
int main() {
int n;
cin >> n;
int u, v;
for(int i = 1; i < n; i++){
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
int mn = inf;
for(int i = 1; i <= n; i++){
cin >> a[i];
mn = min(mn, a[i]);
}
if(mn != 1){
cout << mn << "/1";
return 0;
}
ld ans = 1;
dfs2(1, 0);
dfs3(1, 0);
for(int i = 1; i <= n; i++){
ld tmp = ld(a[i]) / ld(x[i] + (a[i] != 1));
if(tmp < ans){
ans = tmp;
P = a[i];
Q = x[i] + (a[i] != 1);
}
}
int G = __gcd(P, Q);
P /= G;
Q /= G;
cout << P << "/" << Q;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
23788 KB |
Output is correct |
2 |
Correct |
12 ms |
23800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
23764 KB |
Output is correct |
2 |
Correct |
13 ms |
23876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
704 ms |
112800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23764 KB |
Output is correct |
2 |
Correct |
835 ms |
178820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
871 ms |
178168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
775 ms |
85748 KB |
Output is correct |
2 |
Correct |
573 ms |
69528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
837 ms |
88708 KB |
Output is correct |
2 |
Correct |
112 ms |
30156 KB |
Output is correct |
3 |
Correct |
891 ms |
182192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
108 ms |
29900 KB |
Output is correct |
2 |
Correct |
767 ms |
86532 KB |
Output is correct |
3 |
Correct |
528 ms |
55368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
732 ms |
83620 KB |
Output is correct |
2 |
Correct |
799 ms |
86796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
792 ms |
86664 KB |
Output is correct |
2 |
Correct |
515 ms |
55344 KB |
Output is correct |