Solution to Xenia and Tree. This is the cleanest i could make it

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vll;
 
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define INF (1<<29)
#define eps (1e-7)
#define MOD (1000000007)
#define mem(arr, val) memset((arr), (int)(val), sizeof (arr))
#define REP(i, a, b) for (int i=a; i<=b; i++)
#define REPn(i, a, b) for (int i=a; i>=b; i--)
#define FOR(i, n) REP(i, 0, n-1)
#define FORn(j, n) REPn(j, n-1, 0)

This is a clean implementation i guess.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vll;
 
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define INF (1<<29)
#define eps (1e-7)
#define MOD (1000000007)
#define mem(arr, val) memset((arr), (int)(val), sizeof (arr))
#define REP(i, a, b) for (int i=a; i<=b; i++)
#define REPn(i, a, b) for (int i=a; i>=b; i--)
#define FOR(i, n) REP(i, 0, n-1)
#define FORn(j, n) REPn(j, n-1, 0)

Lecture on Centroid Decomposition by Tanuj Khattar. His blog in quora is linked above so i thought i should link this recent video.

Implementation of centroid decomposition on a tree. This is the cleanest implementation i could find on the internet.

Kruskal and Binary Search Solution

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vll;
 
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define INF (1<<29)
#define eps (1e-7)
#define MOD (1000000007)
#define mem(arr, val) memset((arr), (int)(val), sizeof (arr))
#define REP(i, a, b) for (int i=a; i<=b; i++)
#define REPn(i, a, b) for (int i=a; i>=b; i--)
#define FOR(i, n) REP(i, 0, n-1)
#define FORn(j, n) REPn(j, n-1, 0)

my solution is easier to understand i guess.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vll;
 
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define INF (1<<29)
#define MOD (1000000007)
#define mem(arr, val) memset((arr), (int)(val), sizeof (arr))
#define REP(i, a, b) for (int i=a; i<=b; i++)
#define REPn(i, a, b) for (int i=a; i>=b; i--)
#define FOR(i, n) REP(i, 0, n-1)
#define FORn(j, n) REPn(j, n-1, 0)
#define all(v) v.begin(), v.end()

Best Lecture on MST algorithms

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vll;
 
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define INF (1<<29)
#define MOD (1000000007)
#define mem(arr, val) memset((arr), (int)(val), sizeof (arr))
#define REP(i, a, b) for (int i=a; i<=b; i++)
#define REPn(i, a, b) for (int i=a; i>=b; i--)
#define FOR(i, n) REP(i, 0, n-1)
#define FORn(j, n) REPn(j, n-1, 0)
#define all(v) v.begin(), v.end()
#define allR(v) v.rbegin(), v.rend()
#define deb(x) cerr<<#x<<" : "<<x<<endl;

Thanks for the good problem. Solved it took me a day

If your logic is right but you are getting WA in some cases. Generate the largest case and check what happens

If you are failing case 15. Reread the question several times. I just misunderstood the question otherwise i would have gotten correct in one try.