Submission #72956533

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (a > b) - (a < b);
}
int find(int* array, int size, int query) {
  int l = 0, r = size - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (array[m] == query) return m;
    else if (array[m] < query) l = m + 1;
    else r = m - 1;
  }
  return size;
}
int ec[114514], *es[114514];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int find(int* array, int size, int query) {
	int l = 0, r = size - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (array[m] == query) return m;
		else if (array[m] < query) l = m + 1;
		else r = m - 1;
	}
	return size;
}

int ec[114514], *es[114514];

void ae(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
}

int a[114514];

int* memo[114514];

int all_results[114514];
int* each_results[114514];
int luck[114514];

int calc(int node, int from) {
	int from_id = find(es[node], ec[node], from);
	int ans, i;
	if (memo[node][from_id]) return ~memo[node][from_id];
	if (luck[node] == 0) {
		/* 全ての子について未調査 */
		all_results[node] = 0;
		luck[node] = -1;
		for (i = 0; i < ec[node]; i++) {
			if (i != from_id) {
				each_results[node][i] = calc(es[node][i], node);
				if (each_results[node][i] > 0) all_results[node] += each_results[node][i];
			} else {
				each_results[node][i] = 0;
				luck[node] = i + 1;
			}
		}
	} else if (luck[node] > 0) {
		/* 1個の子について未調査 */
		each_results[node][luck[node] - 1] = calc(es[node][luck[node] - 1], node);
		if (each_results[node][luck[node] - 1] > 0) all_results[node] += each_results[node][luck[node] - 1];
		luck[node] = -1;
	}
	ans = a[node] + all_results[node];
	if (from_id < ec[node] && each_results[node][from_id] > 0) ans -= each_results[node][from_id];
	return ~(memo[node][from_id] = ~ans);
}

int main(void) {
	int n, i;
	int ans;
	if (scanf("%d", &n) != 1) return 1;
	for (i = 1; i <= n; i++) {
		int s;
		if (scanf("%d%d", &s, &a[i]) != 2) return 1;
		if (s != 0) {
			ae(s, i);
			ae(i, s);
		}
	}
	for (i = 1; i <= n; i++) {
		if (ec[i] > 0) {
			qsort(es[i], ec[i], sizeof(*es[i]), cmp);
			each_results[i] = malloc(sizeof(*each_results[i]) * ec[i]);
		}
		memo[i] = calloc(ec[i] + 1, sizeof(*memo[i]));
	}
	ans = calc(1, 0);
	for (i = 2; i <= n; i++) {
		int candidate = calc(i, 0);
		if (candidate > ans) ans = candidate;
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result