比赛 EYOI与SBOI开学欢乐赛3rd 评测结果 AAAAAAAAAA
题目名称 van玩galgame 最终得分 100
用户昵称 ZRQ 运行时间 2.878 s
代码语言 C++ 内存使用 51.51 MiB
提交时间 2022-09-05 20:26:27
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1000010;
struct edge
{
	int to;
	long long w;
};
long long n,ans,dis[N],mx1[N],mx2[N];
int sig;
char ch;
inline void read(long long &x){x=0;sig=1;ch=getchar();while(ch<48||ch>57){if(ch==45)sig=-1;ch=getchar();}while(ch>47&&ch<58){x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}x*=sig;}
vector<edge> edg[N];
void prework(int nw,int sum)
{
	dis[nw]=sum;
	for(int i=0;i<edg[nw].size();++i)
		prework(edg[nw][i].to,edg[nw][i].w+sum);
	return ;
}
void DFS(int nw)
{
	for(int i=0,nxt;i<edg[nw].size();++i)
	{
		nxt=edg[nw][i].to;
		DFS(nxt);
		if(mx1[nxt]+edg[nw][i].w>mx1[nw]) mx2[nw]=mx1[nw],mx1[nw]=mx1[nxt]+edg[nw][i].w;
		else if(mx1[nxt]+edg[nw][i].w>mx2[nw]) mx2[nw]=mx1[nxt]+edg[nw][i].w;
	}
	ans=max(ans,dis[nw]+mx1[nw]+mx2[nw]);
	return ;
}
int main()
{
	freopen("galgame.in","r",stdin);
	freopen("galgame.out","w",stdout); 
	read(n);
	long long k,u,v;
	for(int i=1;i<=n;++i)
	{
		read(k);
		for(int j=1;j<=k;++j)
		{
			read(u),read(v);
			edg[i].push_back((edge){(int)v,u});
		}
	}
	prework(1,0);
	DFS(1);
	printf("%lld",ans);
	return 0;
}