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