#include "citymapping.h"
//#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1tst"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf=1e18;
const int mod2 = 1e9+7;
//const int base=67;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en;
ll kk;
ll el = 19;/*
main()
{
///top1tst
if(fopen(task2".inp","r"))
{
fin(task2);
fou(task2);
}
///top1tst
if(fopen(task".inp","r"))
{
fin(task);
fou(task);
}
///top1tst
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
// cin>>s1;
// int t;cin>>t;while(t--)
phongbeo();
checktime
///top1tst
}
static int N, Q, S, twok[1005][11], depth[1005], curQ, target = 6500;
static long long dist[1005];
static vector< pair<int, int> > adjlist[1005];
static vector< pair< pair<int, int>, int > > edgelist, user_edgelist;
static void dfs(int x, int p, long long d, int dep)
{
dist[x] = d;
depth[x] = dep;
twok[x][0] = p;
for (int i = 1; i <= 10; i++)
{
if (twok[x][i - 1] == -1) break;
twok[x][i] = twok[twok[x][i - 1]][i - 1];
}
for (int i = 0; i < (int)adjlist[x].size(); i++)
{
if (adjlist[x][i].first == p) continue;
dfs(adjlist[x][i].first, x, d + adjlist[x][i].second, dep + 1);
}
}
static int lca(int x, int y)
{
if (depth[x] > depth[y]) swap(x, y);
int dd = depth[y] - depth[x];
for (int i = 0; i <= 10; i++) if (dd & (1 << i)) y = twok[y][i];
if (x == y) return x;
for (int i = 10; i >= 0; i--)
{
if (twok[x][i] != twok[y][i])
{
x = twok[x][i];
y = twok[y][i];
}
}
return twok[x][0];
}
long long get_distance(int X, int Y)
{
if (X <= 0 || X > N || Y <= 0 || Y > N)
{
printf("Wrong Answer: get_distance() arguments out of range.\n");
exit(0);
}
curQ++;
if (curQ > Q)
{
printf("Wrong Answer: Too many calls to get_distance().\n");
exit(0);
}
return dist[X-1] + dist[Y-1] - dist[lca(X-1, Y-1)] * 2;
}*/
ll dp[1001][1001];
ll get(int x,int y)
{
if(x==y) return 0;
if(dp[x][y]==-1)dp[x][y]=dp[y][x]=get_distance(x,y);
return dp[x][y];
}
bool cmp(int a,int b)
{
return get(1,a)<get(1,b);
}
int heavy[100001];
bool nouse[1001];
vector<int> v[100001];
int dfs(int x,int y)
{
int mxz=0,sz=1;
heavy[x]=0;
for(auto f:v[x])
if(!nouse[f])
{
int s=dfs(f,x);
sz+=s;
if(s>mxz)
mxz=s,heavy[x]=f;
}
return sz;
}
void find_roads(int n, int q, int a[], int b[], int cost[])
{
vector<int> vv;
for(int i=2; i<=n; i++)
vv.pb(i);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
dp[i][j]=-1;
sort(vv.begin(),vv.end(),cmp);
for(auto x:vv)
{
memset(nouse,0,sizeof nouse);
dem2=0;
while(true)
{
dfs(1,0);
s2=1;
vector<int>hld;
while(s2!=0)hld.pb(s2),s2=heavy[s2];
if(v[hld.back()].size()!=0)
{
v[hld.back()].pb(x);
a[dem]=hld.back();
b[dem]=x;
cost[dem]=get(1,x)-get(1,hld.back());
dem++;
break;
}
bool de=0;
while(true)
{
s3=hld.back();
if(get(1,s3)+get(s3,x)!=get(1,x))nouse[s3]=1,hld.pop_back();
else
{
if(v[s3].size()==0)
{
v[s3].pb(x);
a[dem]=s3;
b[dem]=x;
cost[dem]=get(1,x)-get(1,s3);
dem++;
de=1;
}
break;
}
}
if(de) break;
}
}
}/*
int a, b;
void phongbeo()
{
cin>>N>>Q>>S;
for (int i = 0; i < N - 1; i++)
{
cin>>a>>b>>w;
a--;
b--;
adjlist[a].push_back(make_pair(b, w));
adjlist[b].push_back(make_pair(a, w));
edgelist.push_back(make_pair(make_pair(min(a, b) + 1, max(a, b) + 1), w));
}
sort(edgelist.begin(), edgelist.end());
memset(twok, -1, sizeof(twok));
dfs(0, -1, 0, 0);
int A[N-1], B[N-1], W[N-1];
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
memset(W, 0, sizeof(W));
find_roads(N, Q, A, B, W);
for (int i = 0; i < N-1; i++) user_edgelist.push_back(make_pair(make_pair(min(A[i], B[i]), max(A[i], B[i])), W[i]));
sort(user_edgelist.begin(), user_edgelist.end());
if (edgelist != user_edgelist)
{
printf("Wrong Answer: Reported list of edges differ from actual.\n");
exit(0);
}
if (S <= 4)
{
printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
exit(0);
}
else
{
if (curQ <= target) printf("Score: 100.00%%\nCorrect: %d out of %d queries used.\n", curQ, Q);
else if (curQ >= 12000) printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (10.0-10.0*((double)(curQ - 12000) / 13000)) / 43 * 100, curQ, Q);
else printf("Score: %.2lf%%\nCorrect: %d out of %d queries used.\n", (40.0-30.0*((double)(curQ - target) / (12000 - target))) / 43 * 100, curQ, Q);
}
}*/
