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