import java.io.*;
import java.util.*;
public class designated_cities {
static int n, timer, tin[], tout[], col[];
static long down[], up[], maxDown[], maxNotInSub[];
static ArrayList<Edge>[] adj;
static ArrayList<Integer>[] subTrees;
static long totalUp, totalDown;
static TreeMap<Long, Integer> map;
static class Edge {
int v, cost1, cost2;
Edge(int a, int b, int c) {
v = a;
cost1 = b;
cost2 = c;
}
}
static void dfs(int u, int p, int id) {
tin[u] = timer++;
maxDown[u] = down[u];
col[u] = id;
subTrees[id].add(u);
int newId = id;
for (Edge nxt : adj[u]) {
int v = nxt.v;
if (v == p)
continue;
up[v] = up[u] + nxt.cost2;
totalUp += nxt.cost2;
down[v] = down[u] + nxt.cost1;
totalDown += nxt.cost1;
dfs(v, u, p == -1 ? ++newId : newId);
maxDown[u] = Math.max(maxDown[u], maxDown[v]);
}
tout[u] = timer - 1;
map.put(down[u], map.getOrDefault(down[u], 0) + 1);
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner();
PrintWriter out = new PrintWriter(System.out);
n = sc.nextInt();
adj = new ArrayList[n];
tin = new int[n];
tout = new int[n];
down = new long[n];
col = new int[n];
up = new long[n];
maxNotInSub = new long[n];
maxDown = new long[n];
map = new TreeMap<Long, Integer>();
subTrees = new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList();
subTrees[i] = new ArrayList();
}
for (int i = 1; i < n; i++) {
int u = sc.nextInt() - 1, v = sc.nextInt() - 1, c1 = sc.nextInt(), c2 = sc.nextInt();
adj[u].add(new Edge(v, c1, c2));
adj[v].add(new Edge(u, c2, c1));
}
dfs(0, -1, 0);
long[] ans = new long[n + 1];
for (int u = 0; u < n; u++) {
ans[1] = Math.max(ans[1], totalUp - up[u] + down[u]);
}
for (int col = 1; col < n; col++) {
for (int u : subTrees[col]) {
map.put(down[u], map.get(down[u]) - 1);
if (map.get(down[u]) == 0)
map.remove(down[u]);
}
long max = map.lastKey();
for (int u : subTrees[col]) {
map.put(down[u], map.getOrDefault(down[u], 0) + 1);
maxNotInSub[u] = max;
}
}
// System.out.println(Arrays.toString(maxNotInSub));
for (int u = 1; u < n; u++) {
long curr = 0;
// u and root
curr = totalUp + down[u];
ans[2] = Math.max(ans[2], curr);
// u and some child for u
curr = totalUp - up[u] + maxDown[u];
ans[2] = Math.max(ans[2], curr);
// u and some node v such that lca(v,u) = root
curr = totalUp + down[u] + maxNotInSub[u];
ans[2] = Math.max(ans[2], curr);
}
int q = sc.nextInt();
while (q-- > 0) {
out.println(totalUp + totalDown -ans[sc.nextInt()]);
}
out.close();
}
static class Scanner {
BufferedReader br;
StringTokenizer st;
Scanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
Scanner(String fileName) throws FileNotFoundException {
br = new BufferedReader(new FileReader(fileName));
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
String nextLine() throws IOException {
return br.readLine();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(next());
}
double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(next());
}
boolean ready() throws IOException {
return br.ready();
}
}
}
Compilation message
Note: designated_cities.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
9944 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
9820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
9760 KB |
Output is correct |
| 2 |
Execution timed out |
2111 ms |
155880 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
9820 KB |
Output is correct |
| 2 |
Execution timed out |
2129 ms |
156008 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
9944 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
9820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
9760 KB |
Output is correct |
| 2 |
Execution timed out |
2111 ms |
155880 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
9944 KB |
Output is correct |
| 2 |
Incorrect |
91 ms |
9820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
