RT

TLE#9

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;i++)
inline ll r() {
	ll x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	return x*f;
}
#define d r()
ll n;
ll x[100010],y[100010],w[100010],ds[100010];
ll fa[100010],sz[100010],c[100010];
vector<ll>e[100010];
ll ans;
ll sum[100010];
void dfs(ll u,ll fat){
	fa[u]=fat,sz[u]=c[u];
	for(int i=0;i<e[u].size();i++)
		if(e[u][i]!=fat)
			dfs(e[u][i],u),sz[u]+=sz[e[u][i]];
}
void Dfs(ll u,ll fat){
	for(int i=0;i<e[u].size();i++)
		if(e[u][i]!=fat)
			sum[e[u][i]]=sum[u]+(sz[1]-2*sz[e[u][i]])*ds[e[u][i]],Dfs(e[u][i],u);
}
int main(){
	n=d;
	f(i,1,n)c[i]=d;
	f(i,1,n-1)x[i]=d,y[i]=d,w[i]=d,e[x[i]].push_back(y[i]),e[y[i]].push_back(x[i]);
	dfs(1,0);
	f(i,1,n-1){
		if(fa[x[i]]==y[i])ds[x[i]]=w[i];
		else ds[y[i]]=w[i];
	}
	f(i,1,n){
		ll dis=0,u=i;
		while(u!=1){dis+=ds[u],u=fa[u];}
		ans+=c[i]*dis;
	}
	sum[1]=ans;
	Dfs(1,0);
	f(i,1,n)ans=min(ans,sum[i]);
	printf("%lld",ans);
	return 0;
}