比赛 |
EYOI与SBOI开学欢乐赛3rd |
评测结果 |
AAAAAAAAAA |
题目名称 |
van玩galgame |
最终得分 |
100 |
用户昵称 |
HeSn |
运行时间 |
3.933 s |
代码语言 |
C++ |
内存使用 |
75.35 MiB |
提交时间 |
2022-09-05 21:31:44 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1000010;
int n, f[MAXN], dp[MAXN], dp2[MAXN], maxn, pos;
vector<int> cd[MAXN], val[MAXN];
bool vis[MAXN];
inline int read(){
int ans=0,sgn=1;
char ch=getchar();
while(!isdigit(ch)){
if (ch=='-')sgn=-1;
ch=getchar();
}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*sgn;
}
void dfs(int x) {
for(int i = 0; i < cd[x].size(); i ++) {
int u = cd[x][i];
dp[u] = dp[x] + val[x][i];
dfs(u);
}
}
void dfs2(int x) {
for(int i = 0; i < cd[x].size(); i ++) {
int u = cd[x][i];
if(vis[u]) {
dfs2(u);
continue;
}
dp2[u] = dp2[x] + val[x][i];
dfs2(u);
}
}
signed main() {
freopen("galgame.in", "r", stdin);
freopen("galgame.out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i ++) {
int k;
k = read();
if(k == 0) {
continue;
}
for(int j = 1; j <= k; j ++) {
int x, w;
w = read();
x = read();
cd[i].push_back(x);
val[i].push_back(w);
f[x] = i;
}
}
dfs(1);
for(int i = 1; i <= n; i ++) {
if(dp[i] > maxn) {
maxn = dp[i];
pos = i;
}
}
while(pos) {
vis[pos] = 1;
pos = f[pos];
}
dfs2(1);
int maxm = 0;
for(int i = 1; i <= n; i ++) {
maxm = max(maxm, dp2[i]);
}
printf("%lld", maxn + maxm);
return 0;
}