比赛 EYOI与SBOI开学欢乐赛3rd 评测结果 AAWWWWWTTT
题目名称 van玩galgame 最终得分 20
用户昵称 Lesater 运行时间 4.366 s
代码语言 C++ 内存使用 43.88 MiB
提交时间 2022-09-05 21:20:06
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll rrrr;
struct data{
    int to;
    ll len;
    ll all;
};
struct Node{
    vector<data> ch;
    ll b1,b2;
};
Node tree[1000000];
int dfs(int now,ll cnt)
{
    ll ans=cnt;
    if(tree[now].ch.size()==0) return cnt;
    for(int i=0;i<tree[now].ch.size();++i)
    {
        tree[now].ch[i].all=dfs(tree[now].ch[i].to,tree[now].ch[i].len);
        ans=max(ans,cnt+tree[now].ch[i].all);
    }
    return ans;
}
bool cmp(data a,data b)
{
    return a.all>b.all;
}
void best(int now,int asd)
{
    if(tree[now].ch.size()==0) return; 
    rrrr=max(rrrr,asd+tree[now].b1+tree[now].b2);      
    for(int i=0;i<tree[now].ch.size();++i)
        best(tree[now].ch[i].to,asd+tree[now].ch[i].len);
    return;
}
int main()
{
    freopen("galgame.in","r",stdin);
    freopen("galgame.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;++j)
        {
            data a;
            cin>>a.len>>a.to;
            a.all=0;
            tree[i].ch.push_back(a);
        }
    }
    dfs(1,0);
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<tree[i].ch.size();++j)
        {     
            if(tree[i].ch[j].all>tree[i].b2)
            {
                tree[i].b2=tree[i].ch[j].all;
                if(tree[i].b2>tree[i].b1) swap(tree[i].b1,tree[i].b2);
            }
        }
    }
    best(1,0);
    cout<<rrrr<<endl;
    return 0;
}