$n = 30$ 时就炸掉了！

#include<bits/stdc++.h>
#define N 105
#define M 1e9
using namespace std;
int ans,n,w,g = 1,to,u,minn,c,fa,fs,es;
vector <int> e[N];
struct Node
{
	int a,v,f;
};
vector <Node> f;
struct No
{
	int to,v;
};
vector <No> t[N];
bool vis[N];
void dfs(int x,int r,int fa)
{
	if(r > ans)
	{
		ans = r;
		u = x;
	}
	int ts = t[x].size();
	for(int i = 0;i < ts;i ++)
	{
		if(fa == t[x][i].to) continue;
		dfs(t[x][i].to,t[x][i].v + r,x);
	}
	return;
}
int main()
{
	freopen("475718_3.in","r",stdin);
//	freopen("475718_3.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
//	cout << n << endl;
	for(int i = 1;i <= n;i ++)
	{
		e[i].push_back(0);
		for(int j = i + 1;j <= n;j ++)
		{
			cin >> w;
			e[i].push_back(w);
			e[j].push_back(w);
		}
	}
	es = e[1].size();
	for(int i = 1;i < es;i ++)
	{
		w = e[1][i],to = i + 1;
		f.push_back((Node){to,w,1});
	}
	vis[1] = 1;
	while(g < n)
	{
		minn = M,c = 0,fa = 0;
		fs = f.size();
		for(int i = 0;i < fs;i ++)
		{
			if(vis[f[i].a])
			{
				f.erase(f.begin() + i);
				i --;
				continue;
			}
			if(minn > f[i].v)
			{
				c = f[i].a;
				minn = f[i].v;
				fa = f[i].f;
//				cout << fa << ' ' << c << endl;
			}
		}
//		cout << fa << ' ' << c << endl;
//		cout << minn << endl;
		t[fa].push_back((No){c,minn});
		cout << "NO\n";
		t[c].push_back((No){fa,minn});
		cout << "OK\n";
		g ++;
		es = e[c].size();
		for(int i = 0;i < es;i ++)
		{
			w = e[c][i],to = i + 1;
			if(to == c) continue;
			f.push_back((Node){to,w,c});
		}
		vis[c] = 1;
	}
//	cout << "OK\n";
	dfs(1,0,0);
	dfs(u,0,0);
	cout << ans << endl;
	return 0;
}