比赛 EYOI与SBOI开学欢乐赛3rd 评测结果 AAAAAAAAAA
题目名称 van玩galgame 最终得分 100
用户昵称 00000 运行时间 3.671 s
代码语言 C++ 内存使用 66.77 MiB
提交时间 2022-09-05 21:02:45
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll p[2000000];
vector<ll> k[2000000];
ll mx,ans;
ll tag,flag;
inline ll read(){
    ll 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(ll x,ll s)
{
    if(s>mx) tag=x;
	mx=max(mx,s);
	for(ll q:k[x])
	{
		dfs(q,s+p[q]);
	}
}
void change(ll x)
{
	if(x==tag)
	{
		p[x]=0;
		flag=1;return;
	}
	for(ll q:k[x])
	{
		change(q);
		if(flag==1)
		{
			p[x]=0;return;
		}
	}
}

int main(){
	freopen("galgame.in","r",stdin);
	freopen("galgame.out","w",stdout);
cin>>n;
for(int q=1;q<=n;q++)
{
	ll x,y,z;
	x=read();
	for(int w=1;w<=x;w++)
	{
		y=read(),z=read();//z是儿子,y是快乐值 
		k[q].push_back(z);
		p[z]=y;
	}
}
dfs(1,0);
change(1);
ans=mx;mx=0;
dfs(1,0);
ans+=mx;
cout<<ans;
//for(int q=1;q<=n;q++) cout<<p[q]<<endl;
return 0;
}