Description：

有一个 $n$ 个点的树，其中每条边有一个正整数边权，知道每两点间最短路长度，判断是否存在一棵树满足条件。

$n\leqslant2000$

Solution：

首先在树上有 $d[a][b]\leqslant d[a][c]+d[c][b]$ ，发现这个和 $floyed$ 非常像，又发现如果以每两点间最短路长度为邻接矩阵建出来的图的最小生成树一定是原树，于是把最小生成树建出来判断即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 2010

int d[MAXN][MAXN];

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

struct edges

{

	int u,v,w;

}es[MAXN * MAXN];

int tot = 0;

bool cmp_e(edges a,edges b){return a.w < b.w;}

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int dis[MAXN];

void dfs(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dis[e[i].to] == -1)

		{

			dis[e[i].to] = dis[k] + e[i].v;

			dfs(e[i].to);

		}

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= n;++j)

			es[++tot] = (edges){i,j,d[i][j] = rd()};

	for(int i = 1;i <= n;++i)f[i] = i;

	sort(es + 1,es + 1 + tot,cmp_e);

	for(int i = 1;i <= tot;++i)

	{

		if(es[i].u != es[i].v && es[i].w == 0)

		{

			puts("NO");

			return 0;

		}

		if(find(es[i].u) != find(es[i].v))

		{

			f[find(es[i].u)] = find(es[i].v);

			add(es[i].u,es[i].v,es[i].w);

		}

	}

	for(int i = 1;i <= n;++i)

	{

		memset(dis,-1,sizeof(dis));

		dis[i] = 0;

		dfs(i);

		for(int j = 1;j <= n;++j)

		{

			if(d[i][j] != dis[j])

			{

				puts("NO");

				return 0;

			}

		}

	}

	puts("YES");

	return 0;

}