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 <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
using namespace std;
long n, minM = 1000000000, maxP = 0, mag[1000000], pd[1000000] = {}, path[1000000] = {}, pn[1000000] = {};
vector <long> adj[1000000], mi[1000000];
void dfs(int i, int p) {
minM = min(minM, mag[i]);
for (int a : adj[i]) {
if (a != p) {
dfs(a, i);
}
}
if (mag[i] == 1) {
pd[i] = 1;
for (int a : adj[i]) {
if (a != p && mag[a] == 1) {
pd[i] = max(pd[i], pd[a]+1);
}
}
for (int a : adj[i]) {
if (a != p && mag[a] == 1) {
if (pd[a]+1 == pd[i]) {
mi[i].push_back(a);
}
}
}
path[i] = pd[i];
if (mi[i].size() == 1){
long mind = mi[i][0];
for (int a : adj[i]){
if (a != p && mag[a] == 1 && a != mind) {
path[i] = max(path[i], pd[i]+pd[a]);
}
}
for (int a : adj[i]){
if (a != p && mag[a] == 1 && a != mind) {
if (pd[i]+pd[a] == path[i]){
mi[i].push_back(a);
}
}
}
} else if (mi[i].size() > 1){
path[i] = 2*pd[i]-1;
}
maxP = max(path[i], maxP);
}
}
void dfs2(int i, int v){
pn[i] = v;
for (int a : mi[i]) {
dfs2(a, v);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
adj[a-1].push_back(b-1);
adj[b-1].push_back(a-1);
}
for (int i = 0; i < n; i++) {
cin >> mag[i];
}
dfs(0, -1);
if (minM == 1){
for (int i = 0; i < n; i++){
if (path[i] == maxP){
dfs2(i, i+1);
}
}
bool twok = false;
for (int i = 0; i < n; i++){
if (mag[i] == 2){
int count = 0;
for (int a : adj[i]){
if (pn[a] != 0){
count++;
if (count >= 2){
twok = true;
break;
}
}
}
}
}
if (twok){
cout << "2/" << (2*maxP+1);
} else {
cout << "1/" << maxP;
}
} else {
cout << minM << "/1";
}
}
# | 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... |