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