#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> edge[1000]; // {id, distance}
ll total;
namespace sensible{
// O(N)
pair<ll,ll> dfs(int x,int up=-1){
pair<ll,ll> res={0,1};
for (auto y: edge[x]) if (y.first!=up){
auto rec=dfs(y.first,x);
rec.first+=y.second*rec.second;
total+=rec.first*res.second+res.first*rec.second;
res.second+=rec.second;
res.first+=rec.first;
}
return res;
}
}
namespace stupid{
ll depth[1000];
ll sum[1000];
ll p[1000][20];
// O(N)
void prep(int x,int up=-1){
for (int i=1; i<20; i++){
p[x][i]=p[p[x][i-1]][i-1];
}
for (auto y: edge[x]) if (y.first!=up){
sum[y.first]=sum[x]+y.second;
depth[y.first]=depth[x]+1;
p[y.first][0]=x;
prep(y.first,x);
}
}
// O( (logN) * (N^2) )
void distance(int x,int y){
total+=sum[x]+sum[y];
if (depth[x]<depth[y]) swap(x,y);
int lca=x;
for (int i=20; i--;) if ((depth[x]-depth[y])&(1<<i)) x=p[x][i];
for (int i=20; i--;) if (p[x][i]!=p[y][i]) x=p[x][i], y=p[y][i];
if (x!=y) x=p[x][0];
total-=sum[x]*2;
}
}
int main(){
srand(0x539);
int const n=1000;
for (int i=1; i<n; i++){
int j=rand()%i;
ll w=rand()%33333;
edge[i].push_back({j,w});
edge[j].push_back({i,w});
}
total=0;
sensible::dfs(0);
cout<<total<<endl;
total=0;
stupid::prep(0);
for (int i=n; i--;) for (int j=i; j--;) stupid::distance(i,j);
cout<<total<<endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKdmVjdG9yPHBhaXI8bGwsbGw+PiBlZGdlWzEwMDBdOyAvLyB7aWQsIGRpc3RhbmNlfQpsbCB0b3RhbDsKCm5hbWVzcGFjZSBzZW5zaWJsZXsKICAvLyBPKE4pCiAgcGFpcjxsbCxsbD4gZGZzKGludCB4LGludCB1cD0tMSl7CiAgICBwYWlyPGxsLGxsPiByZXM9ezAsMX07CgogICAgZm9yIChhdXRvIHk6IGVkZ2VbeF0pIGlmICh5LmZpcnN0IT11cCl7CiAgICAgIGF1dG8gcmVjPWRmcyh5LmZpcnN0LHgpOwoKICAgICAgcmVjLmZpcnN0Kz15LnNlY29uZCpyZWMuc2Vjb25kOwoKICAgICAgdG90YWwrPXJlYy5maXJzdCpyZXMuc2Vjb25kK3Jlcy5maXJzdCpyZWMuc2Vjb25kOwogICAgICByZXMuc2Vjb25kKz1yZWMuc2Vjb25kOwogICAgICByZXMuZmlyc3QrPXJlYy5maXJzdDsKICAgIH0KCiAgICByZXR1cm4gcmVzOwogIH0KfQoKbmFtZXNwYWNlIHN0dXBpZHsKICBsbCBkZXB0aFsxMDAwXTsKICBsbCBzdW1bMTAwMF07CiAgbGwgcFsxMDAwXVsyMF07CgogIC8vIE8oTikKICB2b2lkIHByZXAoaW50IHgsaW50IHVwPS0xKXsKICAgIGZvciAoaW50IGk9MTsgaTwyMDsgaSsrKXsKICAgICAgcFt4XVtpXT1wW3BbeF1baS0xXV1baS0xXTsKICAgIH0KICAgIGZvciAoYXV0byB5OiBlZGdlW3hdKSBpZiAoeS5maXJzdCE9dXApewogICAgICBzdW1beS5maXJzdF09c3VtW3hdK3kuc2Vjb25kOwogICAgICBkZXB0aFt5LmZpcnN0XT1kZXB0aFt4XSsxOwogICAgICBwW3kuZmlyc3RdWzBdPXg7CiAgICAgIHByZXAoeS5maXJzdCx4KTsKICAgIH0KICB9CgogIC8vIE8oIChsb2dOKSAqIChOXjIpICkKICB2b2lkIGRpc3RhbmNlKGludCB4LGludCB5KXsKICAgIHRvdGFsKz1zdW1beF0rc3VtW3ldOwoKICAgIGlmIChkZXB0aFt4XTxkZXB0aFt5XSkgc3dhcCh4LHkpOwogICAgaW50IGxjYT14OwogICAgZm9yIChpbnQgaT0yMDsgaS0tOykgaWYgKChkZXB0aFt4XS1kZXB0aFt5XSkmKDE8PGkpKSB4PXBbeF1baV07CiAgICBmb3IgKGludCBpPTIwOyBpLS07KSBpZiAocFt4XVtpXSE9cFt5XVtpXSkgeD1wW3hdW2ldLCB5PXBbeV1baV07CiAgICBpZiAoeCE9eSkgeD1wW3hdWzBdOwoKICAgIHRvdGFsLT1zdW1beF0qMjsKICB9Cn0KCmludCBtYWluKCl7CiAgc3JhbmQoMHg1MzkpOwoKICBpbnQgY29uc3Qgbj0xMDAwOwogIGZvciAoaW50IGk9MTsgaTxuOyBpKyspewogICAgaW50IGo9cmFuZCgpJWk7CiAgICBsbCB3PXJhbmQoKSUzMzMzMzsKICAgIGVkZ2VbaV0ucHVzaF9iYWNrKHtqLHd9KTsKICAgIGVkZ2Vbal0ucHVzaF9iYWNrKHtpLHd9KTsKICB9CgogIHRvdGFsPTA7CiAgc2Vuc2libGU6OmRmcygwKTsKICBjb3V0PDx0b3RhbDw8ZW5kbDsKCiAgdG90YWw9MDsKICBzdHVwaWQ6OnByZXAoMCk7CiAgZm9yIChpbnQgaT1uOyBpLS07KSBmb3IgKGludCBqPWk7IGotLTspIHN0dXBpZDo6ZGlzdGFuY2UoaSxqKTsKICBjb3V0PDx0b3RhbDw8ZW5kbDsKfQ==