Go to diff to previous submission
import java.io.InputStreamReader; import java.io.BufferedReader; import java.util.*; public class Fr { { while (br.ready()) { node[] nodes = new node[n+1]; boolean[] visited = new boolean[n+1]; for (int i = 1; i<=n; i++) { nodes[i] = new node(i); } for (int i = 0; i < n-1; i++) { pipe tem = new pipe(w,nodes[u],nodes[v]); nodes[u].pipes.add(tem); nodes[v].pipes.add(tem); } Stack<node> st = new Stack<node>(); st.push(root); int curcost = 0; while (!st.empty()) { node cur = st.pop(); for (pipe p : cur.pipes) { if (p.equals(cur.in)) continue; if (!p.top.equals(cur)) { node temp = p.top; p.top = p.bottom; p.bottom = temp; } p.bottom.in = p; if (!p.bottom.equals(cur)) { st.push(p.bottom); } } if (cur.pipes.size() == 1&& !cur.equals(root)) { curcost += cur.in.val; } } st.push(root); while (!st.empty()) { node cur = st.pop(); visited[cur.n] = true; boolean allkidsvisted = true; for (pipe p : cur.pipes) { if (p.equals(cur.in)) continue; allkidsvisted &= visited[p.bottom.n]; } if (!allkidsvisted) { st.push(cur); for (pipe p : cur.pipes) { if (p.equals(cur.in)) continue; st.push(p.bottom); } } else { cur.necvalve = 0; if (cur.equals(root)) continue; for (pipe p : cur.pipes) { if (p.equals(cur.in)) continue; cur.necvalve += p.val; cur.necvalve += p.bottom.necvalve; } if (cur.in.val < cur.necvalve) { curcost -= cur.necvalve; curcost += cur.in.val; } } } } } public static class node { pipe in; ArrayList<pipe> pipes; int n; int necvalve; public node(int nn) { necvalve = 0; pipes = new ArrayList<pipe>(); n = nn; } } public static class pipe { int val; node top; node bottom; public pipe(int v,node t,node b) { val = v; top = t; bottom = b; } } }
--- c5.s1032.cteam099.fr.java.0.Fr.java +++ c5.s1053.cteam099.fr.java.0.Fr.java @@ -37,8 +37,4 @@ { node cur = st.pop(); - if (cur.pipes.size() == 1) - { - curcost += cur.in.val; - } for (pipe p : cur.pipes) { @@ -56,4 +52,8 @@ } } + if (cur.pipes.size() == 1&& !cur.equals(root)) + { + curcost += cur.in.val; + } } st.push(root);