比赛 EYOI与SBOI开学欢乐赛3rd 评测结果 AAAAAAAAAA
题目名称 van玩galgame 最终得分 100
用户昵称 yrtiop 运行时间 0.808 s
代码语言 C++ 内存使用 12.60 MiB
提交时间 2022-09-05 20:26:18
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back
typedef long long ll;

int read() {
	int s = 0,f = 1;
	char c = getchar();
	for(;c < '0'||c > '9';c = getchar())
		if(c == '-')f = -1;
	for(;c >= '0'&&c <= '9';c = getchar())
		s = (s << 1) + (s << 3) + (c ^ '0');
	return s * f; 
}

const ll INF = 1e18;
const int maxn = 1e6 + 5;
int head[maxn],ver[maxn],nxt[maxn],dist[maxn],cnt;

void add(int u,int v,int t) {
	ver[++ cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
	dist[cnt] = t;
	return ;
}

int n;
ll ans;

ll dfs(int u,ll dep) {
	ll Max = 0ll,t;
	for(int i = head[u];i;i = nxt[i]) {
		int v = ver[i],w = dist[i];
		t = dfs(v , dep + w);
		ans = std::max(ans , dep + Max + std::max(0ll , t + w));
		Max = std::max(Max , t + w); 
	} 
	
	return Max;
}

int main() {
	freopen("galgame.in","r",stdin);
	freopen("galgame.out","w",stdout);
	n = read();
	for(int i = 1;i <= n;++ i) {
		int m = read();
		for(;m;-- m) {
			int t = read(),v = read();
			add(i , v , t);
		}
	}
	
	ans = -INF;
	dfs(1 , 0);
	
	printf("%lld",ans);
	return 0;
}