import java.io.*;
import java.util.*;
public class mag {
static int n, minM = Integer.MAX_VALUE, maxP = 0;
static int[] mag, pd, path, pn, par;
static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(), mi = new ArrayList<ArrayList<Integer>>();
static ArrayList<Integer> mPis = new ArrayList<Integer>(), twos = new ArrayList<Integer>();
static void dfs(int i, int p) {
minM = Integer.min(minM, mag[i]);
for (int a : adj.get(i)) {
if (a != p) {
dfs(a, i);
}
}
if (mag[i] == 1) {
pd[i] = 1;
for (int a : adj.get(i)) {
if (a != p && mag[a] == 1) {
if (pd[a]+1 > pd[i]) {
pd[i] = pd[a]+1;
ArrayList<Integer> t= new ArrayList<Integer>();
t.add(a);
mi.set(i, t);
} else if (pd[a]+1 == pd[i]) {
mi.get(i).add(a);
}
}
}
ArrayList<Integer> minds = mi.get(i);
path[i] = pd[i];
if (minds.size() == 1){
int mind = minds.get(0);
ArrayList<Integer> t = new ArrayList<Integer>();
for (int a : adj.get(i)){
if (a != p && mag[a] == 1 && a != mind ) {
if (pd[i]+pd[a] > path[i]){
path[i] = pd[i]+pd[a];
t = new ArrayList<Integer>();
t.add(a);
} else if (pd[i]+pd[a] == path[i]){
t.add(a);
}
}
}
minds.addAll(t);
} else if (minds.size() > 1){
path[i] = 2*pd[i]-1;
}
if (path[i] > maxP){
maxP = path[i];
mPis = new ArrayList<Integer>();
mPis.add(i);
} else if (path[i] == maxP){
mPis.add(i);
}
} else if (mag[i] == 2){
twos.add(i);
}
}
static void dfs2(int i, int v){
pn[i] = v;
for (int a : mi.get(i)) {
dfs2(a, v);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
n = Integer.parseInt(br.readLine());
mag = new int[n];
for (int i = 0; i < n; i++) {
mi.add(new ArrayList<Integer>());
adj.add(new ArrayList<Integer>());
}
for (int i = 0; i < n-1; i++) {
String[] line = br.readLine().split(" ");
int a = Integer.parseInt(line[0])-1, b = Integer.parseInt(line[1])-1;
adj.get(a).add(b);
adj.get(b).add(a);
}
for (int i = 0; i < n; i++) {
mag[i] = Integer.parseInt(br.readLine());
}
pd = new int[n];
path = new int[n];
dfs(0, -1);
if (minM == 1){
pn = new int[n];
for (int a : mPis){
dfs2(a, a+1);
}
boolean twok = false;
for (int i : twos){
HashSet<Integer> hs = new HashSet<Integer>();
for (int a : adj.get(i)){
if (pn[a] != 0){
hs.add(pn[a]);
}
}
if (hs.size() >= 2){
twok = true;
break;
}
}
if (twok){
pw.println("2/"+(2*maxP+1));
} else {
pw.println("1/"+maxP);
}
} else {
pw.println(minM+"/1");
}
pw.close();
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
121 ms |
12396 KB |
Output is correct |
| 2 |
Correct |
107 ms |
11532 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
140 ms |
12520 KB |
Output is correct |
| 2 |
Correct |
130 ms |
12660 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3981 ms |
262148 KB |
Execution killed with signal 9 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
89 ms |
10308 KB |
Output is correct |
| 2 |
Runtime error |
3911 ms |
262144 KB |
Execution killed with signal 9 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3973 ms |
262144 KB |
Execution killed with signal 9 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4090 ms |
260392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3953 ms |
262152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1148 ms |
78068 KB |
Output is correct |
| 2 |
Runtime error |
3975 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4148 ms |
240032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4050 ms |
262144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
