比赛 |
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;
}