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;
const int md = 1e6 + 10;
typedef pair < long long, int > II;
vector < int > adj[md];
int a[md], u[md], v[md], par[md];
int f[md][5];
queue < int > q;
int n;
long long a1 = 1e9, b1 = 1;
void compare(long long a2, long long b2) {
if (a1 * b2 >= a2 * b1) {
a1 = a2;
b1 = b2;
}
}
void dfs(int u, int root) {
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (par[u] == v) continue;
par[v] = u;
dfs(v, root);
}
//cout << u << "*\n";
int smax1 = 0, fmax1 = 0, smax2 = 0, pmax1 = 0, pmax2 = 0;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (par[u] == v) continue;
if (fmax1 < f[v][0]) {
pmax1 = v;
fmax1 = f[v][0];
}
if (smax2 < f[v][1]) {
smax2 = f[v][1];
pmax2 = v;
}
// cout << "(" << f[v][0] << " " << f[v][1] << ") ";
}
//cout << endl;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (par[u] == v || v == pmax1) continue;
smax1 = max(smax1, f[v][0]);
}
//cout << fmax1 << " " << smax1 << " " << smax2 << endl;
if (a[u] == 1) {
compare(1, 1);
compare(1, smax1 + fmax1 + 1);
if (pmax1 != pmax2)
compare(2, fmax1 + smax2 + 1);
compare(1, fmax1 + 1);
compare(2, smax2 + 1);
if (fmax1 > 0)
f[u][0] = fmax1 + 1;
if (smax2 > 0)
f[u][1] = smax2 + 1;
} else {
compare(2, 1);
compare(2, smax1 + fmax1 + 1);
if (fmax1 > 0)
f[u][1] = fmax1 + 1;
}
//if (a1 == 2 && b1 == 9)
// cout << "false\n";
//cout << f[u][0] << " " << f[u][1] << endl;
}
int main() {
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin >> n;
for(int i = 1; i < n; i++)
cin >> u[i] >> v[i];
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i < n; i++) {
//int u, v;
//cin >> u >> v;
if (a[u[i]] + a[v[i]] <= 3) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
}
for(int i = 1; i <= n; i++) {
f[i][0] = (a[i] == 1);
f[i][1] = (a[i] == 2);
}
for(int i = 1; i <= n; i++)
if (!par[i]) {
if (a[i] >= 3) {
compare(a[i], 1);
continue;
}
//cout << i << endl;
par[i] = i;
dfs(i, i);
}
//for(int i = 1; i <= n; i++)
// cout << i <<" " << f[i][0] << " " << f[i][1] << endl;
int gcd = __gcd(a1, b1);
cout << a1 / gcd << "/" << b1 / gcd;
return 0;
}
Compilation message (stderr)
mag.cpp: In function 'void dfs(int, int)':
mag.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
mag.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
mag.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
# | 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... |