P1364

本人不想优化最近公共祖先

n被傻逼最大范围改成了1000

目前90分，1.143秒

#include <bits/stdc++.h>
using namespace std;
int n,w[1005],ls[1005],rs[1005],fa[1005],dep[1005];
long long minn=2e9;
vector <int> v[1005];
void dfs(int now,int x)
{
	dep[now]=x;
	if (ls[now]!=0)
	{
		dfs(ls[now],x+1);
	}
	if (rs[now]!=0)
	{
		dfs(rs[now],x+1);
	}
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>w[i]>>ls[i]>>rs[i];
		v[i].push_back(ls[i]);
		v[ls[i]].push_back(i);
		v[i].push_back(rs[i]);
		v[rs[i]].push_back(i);
		fa[ls[i]]=i;
		fa[rs[i]]=i;
	}
	dfs(1,1);
	for (int i=1;i<=n;i++)
	{
		long long nans=0;
		for (int j=1;j<=n;j++)
		{
			int x=i,y=j,na=0;
			while (dep[x]!=dep[y])
			{
				if (dep[x]<dep[y])
				{
					y=fa[y];
					na++;
				}
				else
				{
					x=fa[x];
					na++;
				}
			}
			while (x!=y)
			{
				x=fa[x];
				y=fa[y];
				na+=2;
			}
			nans+=na*w[j];
		}
		minn=min(nans,minn);
	}
	cout<<minn;
	return 0;
}