| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 14087 | shuuna | Beads and wires (APIO14_beads) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 200010
#define maxm 400010
using namespace std;
typedef long long LL;
int n,down[maxn],up[maxn],val[maxn],father[maxn];
int nEdge=1,to[maxm],next[maxm],len[maxm],start[maxn];
void make(int a,int b,int c)
{
++nEdge,to[nEdge]=b,next[nEdge]=start[a],start[a]=nEdge,len[nEdge]=c;
}
void read()
{
scanf("%d",&n);
for(int i=2,a,b,c;i<=n;++i)
{
scanf("%d %d %d",&a,&b,&c);
make(a,b,c),make(b,a,c);
}
}
void BFS(int p)
{
static int queue[maxn],in[maxn];
int front=0,rear=1;
queue[rear]=p,father[p]=0;
while(front<rear)
{
int p=queue[++front];
for(int i=start[p];i;i=next[i])
if(to[i]!=father[p])
{
queue[++rear]=to[i];
father[to[i]]=p;
in[to[i]]=len[i];
}
}
for(int i=n;i>=1;--i)
{
int p=queue[i],&ans=down[p];
for(int j=start[p];j;j=next[j])
if(to[j]!=father[p])
{
int q=to[j],tmp=down[q];
for(int k=start[q];k;k=next[k])
if(to[k]!=p)
tmp=max(tmp,down[q]-val[to[k]]+down[to[k]]+len[j]+len[k]);
ans+=tmp,val[q]=tmp;
}
}
for(int i=1;i<=n;++i)
{
int p=queue[i],max1=-1<<30,id=0,max2=-1<<30,v1=0;
if(father[p])
v1=up[father[p]]+down[father[p]]-val[p]+down[p];
for(int j=start[p];j;j=next[j])
if(to[j]!=father[p])
{
int q=to[j],v=down[q]+len[j]-val[q];
up[q]=up[p]+down[p]-val[q];
if(father[p])
up[q]=max(up[q],v1-val[to[j]]+len[j]+in[p]);
if(max1<=v)
max2=max1,max1=v,id=j;
else if(max2<=v)
max2=v;
}
for(int j=start[p];j;j=next[j])
if(to[j]!=father[p])
{
int q=to[j];
if(j==id)
up[q]=max(up[q],up[p]+down[p]-val[q]+max2+len[j]);
else
up[q]=max(up[q],up[p]+down[p]-val[q]+max1+len[j]);
}
}
}
int work()
{
int ans=0;
BFS(1);
for(int i=1;i<=n;++i)
ans=max(ans,up[i]+down[i]);
return ans;
}
int main()
{
//freopen("beads.in","r",stdin);
//freopen("beads.out","w",stdout);
read();
printf("%d\n",work());
//fclose(stdin);
//fclose(stdout);
//system("pause");
return 0;
}