Submission #7824514

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define gc getchar()
#define t(i) edge[i].to
#define w(i) edge[i].wei
#define ri register int
#define rb register bool
#define rc register char
#define lowbit(x) (x&(-x))
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=1e5+10,inf=1e9;
int head[N],ed_cnt,n,sz[N],mxsz[N],rt,d[N],as;
bool flg;
struct ed{int to,nxt,wei;}edge[N<<1];

il int read()
{
	rc ch=gc;ri x=0;rb y=1;
	while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
	if(ch=='-')ch=gc,y=0;
	while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
	return y?x:-x;
}
il void ad(ri x,ri y,ri z)
{edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],z};head[x]=ed_cnt;}
void dfs(ri nw)
{
	sz[nw]=1;mxsz[nw]=0;
	e(i,nw)if(!sz[t(i)])d[t(i)]=w(i),dfs(t(i)),mxsz[nw]=max(mxsz[nw],sz[t(i)]),sz[nw]+=sz[t(i)];
	mxsz[nw]=max(mxsz[nw],n-sz[nw]);
	if(mxsz[nw]<mxsz[rt])rt=nw;
}

signed main()
{
	//freopen("king.in","r",stdin);freopen("king.out","w",stdout);
	n=read();rp(i,1,n-1){ri x=read(),y=read(),z=read();ad(x,y,z);}mxsz[0]=inf;dfs(1);
	rp(i,2,n){ri l=sz[i],r=n-sz[i];if(l==r)flg=1,as+=(2ll*l-1)*d[i];else as+=2ll*min(l,r)*d[i];}
	if(!flg){ri tmp=inf;e(i,rt)tmp=min(tmp,w(i));as-=tmp;}
	printf("%lld\n",as);
	return 0;
}

Submission Info

Judge Result