Submission #1521075

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

int read()
{
	int ans=0;
	char ch=getchar();
	for(;(ch<'0' || ch>'9') && ch!='-';ch=getchar());
	bool flag=0;
	if(ch=='-')flag=1,ch=getchar();
	for(;ch>='0' && ch<='9';ch=getchar())ans=ans*10+ch-'0';
	if(flag)ans=-ans;
	return ans;
}

long long rell()
{
	long long ans=0;
	char ch=getchar();
	for(;(ch<'0' || ch>'9') && ch!='-';ch=getchar());
	bool flag=0;
	if(ch=='-')flag=1,ch=getchar();
	for(;ch>='0' && ch<='9';ch=getchar())ans=ans*10ll+(long long)(ch-'0');
	if(flag)ans=-ans;
	return ans;
}

void writ(int n)
{
	char ch[25];
	int m=0;
	if(n<0)putchar('-'),n=-n;
	if(n==0)
	{
		putchar('0');
		return;
	}
	for(;n;n/=10)ch[m++]=n%10ll+'0';
	for(;m;)putchar(ch[--m]);
}

void wrll(long long n)
{
	char ch[25];
	int m=0;
	if(n<0)putchar('-'),n=-n;
	if(n==0)
	{
		putchar('0');
		return;
	}
	for(;n;n/=10ll)ch[m++]=n%10ll+'0';
	for(;m;)putchar(ch[--m]);
}
const int M=1<<18,big=0x3f3f3f3f;
int st[M],pv[M],p1[M],tot,f[M],size[M];
long long pg[M],mi=big;

void side(int u,int v,int k)
{
	pv[tot]=v;
	pg[tot]=k;
	p1[tot]=st[u];
	st[u]=tot++;
}

void ges(int fa,int u)
{
	//printf("ges %d %d\n",fa,u);
	size[u]=1;
	for(int i=st[u];~i;i=p1[i])if(pv[i]!=fa && f[pv[i]])
	{
		ges(u,pv[i]);
		size[u]+=size[pv[i]];
	}
}

int fi(int fa,int u,int n)
{
	for(int i=st[u];~i;i=p1[i])if(pv[i]!=fa && f[pv[i]])
	{
		int k=fi(u,pv[i],n);
		if(~k)return k;
	}
	if(size[u]>n/2)return u;else return -1;
}

long long query(int fa,int u,long long de)
{
	long long ans=de+de;
	if(de)mi=min(mi,de);
	for(int i=st[u];~i;i=p1[i])if(pv[i]!=fa && f[pv[i]])
	{
		ans+=query(u,pv[i],de+pg[i]);
	}
	return ans;
}

long long work(int u)
{
	//printf("work %d\n",u);
	ges(-1,u);
	//puts("RA");
	u=fi(-1,u,size[u]);
	//puts("RA");
	long long ans=query(-1,u,0);
	//printf("work %d\n",(int)ans);
	/*f[u]=0;
	for(int i=st[u];~i;i=p1[i])if(f[pv[i]])
	{
		ans+=work(pv[i]);
	}*/
	return ans;
}

int main()
{
	int n=read();
	if(n==1)
	{
		puts("0");
		return 0;
	}
	tot=0;
	memset(st,-1,sizeof(st));
	for(int i=1;i<n;i++)
	{
		int u=read()-1,v=read()-1,k=read();
		side(u,v,k);
		side(v,u,k);
		//mi=min(mi,k);
	}
	/*for(int i=0;i<n;i++)
	{
		printf("i=%d st[i]=%d\n",i,st[i]);
	}*/
	memset(f,1,sizeof(f));
	wrll(work(0)-(long long)mi);
	puts("");
	return 0;
}

Submission Info

Judge Result