import java.io.*;
import java.util.*;
// @Jasper
public class fireworks {
static long LINF = (long) 1e18 + 5;
static int INF = (int) 1e9 + 5;
static int MOD = (int) 1e9 + 7;
static int MAX = (int) 3e5 + 5;
static long n, m, ans = 0, a, b;
static long[] plague = new long [MAX];
static long[] root = new long [MAX];
static List <Integer>[] edges = new List[MAX];
static PriorityQueue <Long>[] q = new PriorityQueue [MAX];
public static void dfs(int u){
root[u] = u;
if (u > n){
q[u].add(plague[u]);
q[u].add(plague[u]);
return;
}
for (int v : edges[u]){
dfs(v);
if (q[(int) root[v]].size() > q[(int) root[u]].size())
root[u] = root[v];
}
for (int v : edges[u]){
if (root[u] != root[v]){
while (q[(int) root[v]].size() > 0){
long tmp = q[(int) root[v]].poll();
q[(int) root[u]].add(tmp);
}
}
}
for (int i = 1; i < edges[u].size(); i++)
q[(int) root[u]].poll();
// System.out.println(a + " " + b);
a = q[(int) root[u]].poll();
b = q[(int) root[u]].poll();
a += plague[u];
b += plague[u];
q[(int) root[u]].add(b);
q[(int) root[u]].add(a);
}
//------------------Solution------------------------------------------------
private static void run_case() throws Exception {
n = io.nextInt();
m = io.nextInt();
m += n;
ans = 0;
for (int i = 0; i < MAX; ++i){
edges[i] = new ArrayList <Integer> ();
q[i] = new PriorityQueue <Long> ((x, y) -> Long.compare(y, x));
}
for (int i = 2; i <= m; i++){
a = io.nextInt();
b = io.nextInt();
edges[(int) a].add(i);
plague[i] = b;
ans += b;
}
// System.out.println(ans);
dfs(1);
// System.out.println(a + " " + b);
long tmp = q[(int)root[1]].poll();
a = q[(int)root[1]].peek();
q[(int)root[1]].add((long) 0);
b = 0;
while (q[(int) root[1]].size() > 0){
ans -= (a - q[(int) root[1]].peek()) * b;
b++;
a = q[(int) root[1]].poll();
}
System.out.println(ans);
}
public static void main(String[] args) throws Exception {
int Test = 1;
// Test = io.nextInt();
for (int i = 1; i <= Test; i++){
run_case();
}
io.close();
}
//-----------PrintWriter for faster output---------------------------------
public static FastIO io = new FastIO();
static void sort(int[] a) {
ArrayList<Integer> l = new ArrayList<>();
for (int i : a) l.add(i);
Collections.sort(l);
for (int i = 0; i < a.length; i++) a[i] = l.get(i);
}
public static void swap(int data[], int left, int right) {
int temp = data[left];
data[left] = data[right];
data[right] = temp;
}
public static void reverse(int data[], int left, int right){
while (left < right) {
int temp = data[left];
data[left++] = data[right];
data[right--] = temp;
}
}
public static boolean nextPermutation(int data[]){
if (data.length <= 1)
return false;
int last = data.length - 2;
while (last >= 0) {
if (data[last] < data[last + 1])
break;
last--;
}
if (last < 0)
return false;
int nextGreater = data.length - 1;
for (int i = data.length - 1; i > last; i--) {
if (data[i] > data[last]) {
nextGreater = i;
break;
}
}
swap(data, nextGreater, last);
reverse(data, last + 1, data.length - 1);
return true;
}
//-----------MyScanner class for faster input----------
static class FastIO extends PrintWriter {
private InputStream stream;
private byte[] buf = new byte[1 << 16];
private int curChar, numChars;
// standard input
public FastIO() {
this(System.in, System.out);
}
public FastIO(InputStream i, OutputStream o) {
super(o);
stream = i;
}
// file input
public FastIO(String i, String o) throws IOException {
super(new FileWriter(o));
stream = new FileInputStream(i);
}
// throws InputMismatchException() if previously detected end of file
private int nextByte() {
if (numChars == -1) throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars == -1) return -1; // end of file
}
return buf[curChar++];
}
// to read in entire lines, replace c <= ' '
// with a function that checks whether c is a line break
public String next() {
int c;
do {
c = nextByte();
} while (c <= ' ');
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = nextByte();
} while (c > ' ');
return res.toString();
}
public String nextLine() {
int c;
do {
c = nextByte();
} while (c < '\n');
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = nextByte();
} while (c > '\n');
return res.toString();
}
public int nextInt() {
int c;
do {
c = nextByte();
} while (c <= ' ');
int sgn = 1;
if (c == '-') {
sgn = -1;
c = nextByte();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = 10 * res + c - '0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public long nextLong() {
int c;
do {
c = nextByte();
} while (c <= ' ');
int sgn = 1;
if (c == '-') {
sgn = -1;
c = nextByte();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = 10 * res + c - '0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
//--------------------------------------------------------
}
Compilation message
Note: fireworks.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
54736 KB |
Output is correct |
2 |
Correct |
210 ms |
54312 KB |
Output is correct |
3 |
Correct |
199 ms |
54348 KB |
Output is correct |
4 |
Correct |
218 ms |
54300 KB |
Output is correct |
5 |
Correct |
195 ms |
54464 KB |
Output is correct |
6 |
Correct |
191 ms |
54488 KB |
Output is correct |
7 |
Correct |
206 ms |
54460 KB |
Output is correct |
8 |
Correct |
200 ms |
54424 KB |
Output is correct |
9 |
Correct |
207 ms |
54336 KB |
Output is correct |
10 |
Correct |
193 ms |
54528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
54596 KB |
Output is correct |
2 |
Correct |
203 ms |
54396 KB |
Output is correct |
3 |
Correct |
198 ms |
54336 KB |
Output is correct |
4 |
Correct |
200 ms |
54276 KB |
Output is correct |
5 |
Correct |
213 ms |
54304 KB |
Output is correct |
6 |
Correct |
198 ms |
54472 KB |
Output is correct |
7 |
Correct |
212 ms |
54360 KB |
Output is correct |
8 |
Correct |
221 ms |
54232 KB |
Output is correct |
9 |
Correct |
207 ms |
54320 KB |
Output is correct |
10 |
Correct |
222 ms |
54484 KB |
Output is correct |
11 |
Correct |
211 ms |
54292 KB |
Output is correct |
12 |
Correct |
203 ms |
54316 KB |
Output is correct |
13 |
Correct |
214 ms |
54280 KB |
Output is correct |
14 |
Correct |
200 ms |
54640 KB |
Output is correct |
15 |
Correct |
202 ms |
54492 KB |
Output is correct |
16 |
Correct |
223 ms |
54416 KB |
Output is correct |
17 |
Correct |
201 ms |
54372 KB |
Output is correct |
18 |
Correct |
201 ms |
54404 KB |
Output is correct |
19 |
Correct |
208 ms |
54460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
54736 KB |
Output is correct |
2 |
Correct |
210 ms |
54312 KB |
Output is correct |
3 |
Correct |
199 ms |
54348 KB |
Output is correct |
4 |
Correct |
218 ms |
54300 KB |
Output is correct |
5 |
Correct |
195 ms |
54464 KB |
Output is correct |
6 |
Correct |
191 ms |
54488 KB |
Output is correct |
7 |
Correct |
206 ms |
54460 KB |
Output is correct |
8 |
Correct |
200 ms |
54424 KB |
Output is correct |
9 |
Correct |
207 ms |
54336 KB |
Output is correct |
10 |
Correct |
193 ms |
54528 KB |
Output is correct |
11 |
Correct |
195 ms |
54596 KB |
Output is correct |
12 |
Correct |
203 ms |
54396 KB |
Output is correct |
13 |
Correct |
198 ms |
54336 KB |
Output is correct |
14 |
Correct |
200 ms |
54276 KB |
Output is correct |
15 |
Correct |
213 ms |
54304 KB |
Output is correct |
16 |
Correct |
198 ms |
54472 KB |
Output is correct |
17 |
Correct |
212 ms |
54360 KB |
Output is correct |
18 |
Correct |
221 ms |
54232 KB |
Output is correct |
19 |
Correct |
207 ms |
54320 KB |
Output is correct |
20 |
Correct |
222 ms |
54484 KB |
Output is correct |
21 |
Correct |
211 ms |
54292 KB |
Output is correct |
22 |
Correct |
203 ms |
54316 KB |
Output is correct |
23 |
Correct |
214 ms |
54280 KB |
Output is correct |
24 |
Correct |
200 ms |
54640 KB |
Output is correct |
25 |
Correct |
202 ms |
54492 KB |
Output is correct |
26 |
Correct |
223 ms |
54416 KB |
Output is correct |
27 |
Correct |
201 ms |
54372 KB |
Output is correct |
28 |
Correct |
201 ms |
54404 KB |
Output is correct |
29 |
Correct |
208 ms |
54460 KB |
Output is correct |
30 |
Correct |
203 ms |
54328 KB |
Output is correct |
31 |
Correct |
223 ms |
54484 KB |
Output is correct |
32 |
Correct |
250 ms |
55076 KB |
Output is correct |
33 |
Correct |
327 ms |
63820 KB |
Output is correct |
34 |
Correct |
336 ms |
64140 KB |
Output is correct |
35 |
Correct |
339 ms |
63988 KB |
Output is correct |
36 |
Correct |
341 ms |
63860 KB |
Output is correct |
37 |
Correct |
349 ms |
63772 KB |
Output is correct |
38 |
Correct |
345 ms |
63972 KB |
Output is correct |
39 |
Correct |
360 ms |
63740 KB |
Output is correct |
40 |
Correct |
266 ms |
55260 KB |
Output is correct |
41 |
Correct |
336 ms |
61792 KB |
Output is correct |
42 |
Correct |
312 ms |
61248 KB |
Output is correct |
43 |
Correct |
307 ms |
56460 KB |
Output is correct |
44 |
Correct |
373 ms |
64232 KB |
Output is correct |
45 |
Correct |
424 ms |
64128 KB |
Output is correct |
46 |
Correct |
334 ms |
63456 KB |
Output is correct |
47 |
Correct |
326 ms |
63668 KB |
Output is correct |
48 |
Correct |
344 ms |
63704 KB |
Output is correct |
49 |
Correct |
328 ms |
63636 KB |
Output is correct |
50 |
Correct |
324 ms |
56320 KB |
Output is correct |
51 |
Correct |
290 ms |
56360 KB |
Output is correct |
52 |
Correct |
337 ms |
60172 KB |
Output is correct |
53 |
Correct |
412 ms |
63684 KB |
Output is correct |
54 |
Correct |
279 ms |
54596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
54736 KB |
Output is correct |
2 |
Correct |
210 ms |
54312 KB |
Output is correct |
3 |
Correct |
199 ms |
54348 KB |
Output is correct |
4 |
Correct |
218 ms |
54300 KB |
Output is correct |
5 |
Correct |
195 ms |
54464 KB |
Output is correct |
6 |
Correct |
191 ms |
54488 KB |
Output is correct |
7 |
Correct |
206 ms |
54460 KB |
Output is correct |
8 |
Correct |
200 ms |
54424 KB |
Output is correct |
9 |
Correct |
207 ms |
54336 KB |
Output is correct |
10 |
Correct |
193 ms |
54528 KB |
Output is correct |
11 |
Correct |
195 ms |
54596 KB |
Output is correct |
12 |
Correct |
203 ms |
54396 KB |
Output is correct |
13 |
Correct |
198 ms |
54336 KB |
Output is correct |
14 |
Correct |
200 ms |
54276 KB |
Output is correct |
15 |
Correct |
213 ms |
54304 KB |
Output is correct |
16 |
Correct |
198 ms |
54472 KB |
Output is correct |
17 |
Correct |
212 ms |
54360 KB |
Output is correct |
18 |
Correct |
221 ms |
54232 KB |
Output is correct |
19 |
Correct |
207 ms |
54320 KB |
Output is correct |
20 |
Correct |
222 ms |
54484 KB |
Output is correct |
21 |
Correct |
211 ms |
54292 KB |
Output is correct |
22 |
Correct |
203 ms |
54316 KB |
Output is correct |
23 |
Correct |
214 ms |
54280 KB |
Output is correct |
24 |
Correct |
200 ms |
54640 KB |
Output is correct |
25 |
Correct |
202 ms |
54492 KB |
Output is correct |
26 |
Correct |
223 ms |
54416 KB |
Output is correct |
27 |
Correct |
201 ms |
54372 KB |
Output is correct |
28 |
Correct |
201 ms |
54404 KB |
Output is correct |
29 |
Correct |
208 ms |
54460 KB |
Output is correct |
30 |
Correct |
203 ms |
54328 KB |
Output is correct |
31 |
Correct |
223 ms |
54484 KB |
Output is correct |
32 |
Correct |
250 ms |
55076 KB |
Output is correct |
33 |
Correct |
327 ms |
63820 KB |
Output is correct |
34 |
Correct |
336 ms |
64140 KB |
Output is correct |
35 |
Correct |
339 ms |
63988 KB |
Output is correct |
36 |
Correct |
341 ms |
63860 KB |
Output is correct |
37 |
Correct |
349 ms |
63772 KB |
Output is correct |
38 |
Correct |
345 ms |
63972 KB |
Output is correct |
39 |
Correct |
360 ms |
63740 KB |
Output is correct |
40 |
Correct |
266 ms |
55260 KB |
Output is correct |
41 |
Correct |
336 ms |
61792 KB |
Output is correct |
42 |
Correct |
312 ms |
61248 KB |
Output is correct |
43 |
Correct |
307 ms |
56460 KB |
Output is correct |
44 |
Correct |
373 ms |
64232 KB |
Output is correct |
45 |
Correct |
424 ms |
64128 KB |
Output is correct |
46 |
Correct |
334 ms |
63456 KB |
Output is correct |
47 |
Correct |
326 ms |
63668 KB |
Output is correct |
48 |
Correct |
344 ms |
63704 KB |
Output is correct |
49 |
Correct |
328 ms |
63636 KB |
Output is correct |
50 |
Correct |
324 ms |
56320 KB |
Output is correct |
51 |
Correct |
290 ms |
56360 KB |
Output is correct |
52 |
Correct |
337 ms |
60172 KB |
Output is correct |
53 |
Correct |
412 ms |
63684 KB |
Output is correct |
54 |
Correct |
279 ms |
54596 KB |
Output is correct |
55 |
Correct |
426 ms |
63872 KB |
Output is correct |
56 |
Correct |
463 ms |
69232 KB |
Output is correct |
57 |
Correct |
570 ms |
89156 KB |
Output is correct |
58 |
Correct |
563 ms |
90196 KB |
Output is correct |
59 |
Correct |
639 ms |
91732 KB |
Output is correct |
60 |
Correct |
717 ms |
93220 KB |
Output is correct |
61 |
Correct |
700 ms |
94160 KB |
Output is correct |
62 |
Correct |
741 ms |
101920 KB |
Output is correct |
63 |
Correct |
825 ms |
104428 KB |
Output is correct |
64 |
Correct |
836 ms |
104780 KB |
Output is correct |
65 |
Execution timed out |
2100 ms |
333756 KB |
Time limit exceeded |
66 |
Halted |
0 ms |
0 KB |
- |