#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1000005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
ll n, m[MAXN], dp[MAXN][2];
vector<ll> adj[MAXN];
pair<ll, ll> r = {-1, -1};
void dfs(ll v, ll p){
dp[v][0] = dp[v][1] = -1;
ll z1 = -1, z2 = -1, o1 = -1, o2 = -1;
ll idz = -1, ido = -1;
for(ll v2 : adj[v]) if(v2 != p) {
dfs(v2, v);
if(m[v] >= 3) continue;
if(dp[v2][0] != -1){
if(m[v] == 2){
dp[v][1] = max(dp[v][1], dp[v2][0] + 1);
if(r.first == -1 || r.first * dp[v][1] > 2 * r.second){
r = {2, dp[v][1]};
}
}else if(m[v] == 1){
dp[v][0] = max(dp[v][0], dp[v2][0] + 1);
if(r.first == -1 || r.first * dp[v][0] > r.second){
r = {1, dp[v][0]};
// if(1 + z1 + z2 == 5) cout << "HERE! " << endl;
}
}
if(dp[v2][0] > z1) {
z2 = z1;
z1 = dp[v2][0], idz = v2;
}else if(dp[v2][0] > z2){
z2 = dp[v2][0];
}
}
if(dp[v2][1] != -1){
if(m[v] == 1){
dp[v][1] = max(dp[v][1], dp[v2][1] + 1);
if(r.first == -1 || r.first * dp[v][1] > 2 * r.second){
r = {2, dp[v][1]};
}
}
if(dp[v2][1] > o1) {
o2 = o1;
o1 = dp[v2][1], ido = v2;
}else if(dp[v2][1] > o2){
o2 = dp[v2][1];
}
}
}
if(m[v] == 1){
// 2 on one side, 1 on the other -- MAY CONFLICT
if(ido != idz){
if((z1 != -1 && o1 != -1) && (r.first == -1 || r.first * (1 + z1 + o1) > 2 * r.second)){
r = {2, 1 + z1 + o1};
}
}else{
if((z1 != -1 && o2 != -1) && (r.first == -1 || r.first * (1 + z1 + o2) > 2 * r.second)){
r = {2, 1 + z1 + o2};
// if(r.second == 9) cout << "HERE!" << endl;
}
if((z2 != -1 && o1 != -1) && (r.first == -1 || r.first * (1 + z2 + o1) > 2 * r.second)){
r = {2, 1 + z2 + o1};
}
}
// 1 on both sides -- NO CONFLICT
if((z1 != -1 && z2 != -1) && (r.first == -1 || r.first * (1 + z1 + z2) > r.second)){
r = {1, 1 + z1 + z2};
}
// start own dp[v][0]
dp[v][0] = max(dp[v][0], 1ll);
}
if(m[v] == 2){
// 1 on both sides -- NO CONFLICT
if((z1 != -1 && z2 != -1) && (r.first == -1 || r.first * (1 + z1 + z2) > 2 * r.second)){
r = {2, 1 + z1 + z2};
}
// start own dp[v][1]
dp[v][1] = max(dp[v][1], 1ll);
}
if(m[v] >= 3){
//cout << "HERE with m[v] = " << m[v] << "!!! " << endl;
if(r.first == -1 || r.first > m[v] * r.second){
r = {m[v], 1};
}
}
// cout << v << " v => " << dp[v][0] << ", " << dp[v][1] << endl;
}
int main(){
cin >> n;
FOR(i, 1, n - 1) {
ll a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
FOR(i, 1, n) cin >> m[i];
dfs(1, -1);
if(r.first == 2 && r.second % 2 == 0) r.first /= 2, r.second /= 2;
cout << r.first << "/" << r.second << endl;
}
/*
5
1 2
2 3
3 4
4 5
1
1
2
1
1
7
1 2
2 3
3 4
4 5
5 6
6 7
1
1
1
2
1
1
1
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
25176 KB |
Output is correct |
| 2 |
Correct |
4 ms |
25180 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
25436 KB |
Output is correct |
| 2 |
Correct |
4 ms |
25180 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
497 ms |
133256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
25180 KB |
Output is correct |
| 2 |
Correct |
639 ms |
217428 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
666 ms |
215628 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
545 ms |
93084 KB |
Output is correct |
| 2 |
Correct |
463 ms |
75316 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
626 ms |
97716 KB |
Output is correct |
| 2 |
Correct |
64 ms |
31312 KB |
Output is correct |
| 3 |
Correct |
745 ms |
221328 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
60 ms |
31316 KB |
Output is correct |
| 2 |
Correct |
701 ms |
94112 KB |
Output is correct |
| 3 |
Correct |
412 ms |
61776 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
534 ms |
91412 KB |
Output is correct |
| 2 |
Correct |
676 ms |
94048 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
553 ms |
94672 KB |
Output is correct |
| 2 |
Correct |
349 ms |
61820 KB |
Output is correct |
