Code

#include<iostream>
#include<cmath>
#include<cstdio>
#include<random>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<utility>
#include<unordered_map>
#include<unordered_set>
#include<bitset> 
#define int long long
using namespace std;
constexpr int maxn = 1e6 + 10;
constexpr int maxm = 500 + 10;
constexpr int mod = 998244353;
constexpr int mod1 = 1e9 + 7;
constexpr int inf = 1e18 + 10;
constexpr int dx[] = { 1,-1,0,0 };
constexpr int dy[] = { 0,0,1,-1 };
int n, dis[maxn], dis1[maxn], dis2[maxn], n1, n2, maxd, num[maxn], sum[maxn];
vector<int> edge[maxn];
void dfs(int u, int fa) {
    dis[u] = dis[fa] + 1;
    for (auto v : edge[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
}
void doit1() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dis[0] = -1;
    dfs(1, 0);
    int p = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[p])
            p = i;
    int x = p;
    dfs(x, 0);
    for (int i = 1; i <= n; i++) dis1[i] = dis[i];
    p = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[p])
            p = i;
    maxd = max(maxd, dis[p]);
    dfs(p, 0);
    for (int i = 1; i <= n; i++) dis1[i] = max(dis1[i], dis[i]);
}
void doit2() {
    cin >> n;
    for (int i = 1; i <= n; i++) edge[i].clear();
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dis[0] = -1;
    dfs(1, 0);
    int p = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[p])
            p = i;
    int x = p;
    dfs(x, 0);
    for (int i = 1; i <= n; i++) dis2[i] = dis[i];
    p = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[p])
            p = i;
    maxd = max(maxd, dis[p]);
    dfs(p, 0);
    for (int i = 1; i <= n; i++) dis2[i] = max(dis2[i], dis[i]);
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    doit1(); n1 = n;
    doit2(); n2 = n;
    int ans = 0;
    for (int i = 1; i <= n2; i++)
        num[dis2[i]]++, sum[dis2[i]] += dis2[i];
    for (int i = n2; i >= 0; i--)
        num[i] += num[i + 1], sum[i] += sum[i + 1];
    for (int i = 1; i <= n1; i++) {
        int now = max(0ll, maxd - dis1[i] - 1);
        int cur = num[now];
        ans += sum[now] + cur + cur * dis1[i];
        ans += (n2 - cur) * maxd;
    }
    cout << ans << "\n";
    return 0;
}

#include<iostream>
#include<cmath>
#include<cstdio>
#include<random>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<utility>
#include<unordered_map>
#include<unordered_set>
#include<bitset> 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
constexpr int maxn = 2e5 + 10;
constexpr int maxm = 100 + 10;
constexpr int intinf = 1e9 + 10;
constexpr int mod = 998244353;
constexpr ll inf = 1e15 + 10;
constexpr int dx[] = { 1,-1,0,0 };
constexpr int dy[] = { 0,0,1,-1 };
constexpr ld eps = 1e-12;
using namespace std;

ll n, num[maxn], cnt, siz[maxn], g[maxn], dis[maxn], sum, p;
vector<pair<ll, ll>> edge[maxn];

void add(int u, int v, ll w) {
	edge[u].push_back({ v,w });
}

void find(int u, int fa) {
	siz[u] = num[u];
	bool flag = true;
	for (auto [v, w] : edge[u]) {
		if (v == fa) continue;
		find(v, u);
		if (siz[v] > p / 2) flag = false;
		siz[u] += siz[v];
	}
	if (flag && p - siz[u] <= p / 2)
		g[++sum] = u;
}

void dfs(int u, int fa) {
	for (auto [v, w] : edge[u]) {
		if (v == fa) continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
	}
}

void init() {
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> num[i], p += num[i];
	for (int i = 1; i < n; i++) {
		ll u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	find(1, 0);
	ll ans = inf;
	for (int i = 1; i <= sum; i++) {
		for (int i = 1; i <= n; i++) dis[i] = 0;
		dfs(g[i], 0);
		ll res = 0;
		for (int i = 1; i <= n; i++)
			res += num[i] * dis[i];
		ans = min(ans, res);
	}
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	init();
	return 0;
}

#include<iostream>
#include<cmath>
#include<cstdio>
#include<random>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<utility>
#include<unordered_map>
#include<unordered_set>
#include<bitset> 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
constexpr int maxn = 2e5 + 10;
constexpr int maxm = 100 + 10;
constexpr int intinf = 1e9 + 10;
constexpr int mod = 998244353;
constexpr ll inf = 1e15 + 10;
constexpr int dx[] = { 1,-1,0,0 };
constexpr int dy[] = { 0,0,1,-1 };
constexpr ld eps = 1e-12;
using namespace std;

ll n, num[maxn], cnt, g[maxn], dis[maxn], sum, siz[maxn], ans;
vector<int> edge[maxn];

void add(int u, int v) {
	edge[u].push_back(v);
}

void find(int u, int fa) {
	siz[u] = 1;
	bool flag = true;
	for (auto v : edge[u]) {
		if (v == fa) continue;
		find(v, u);
		if (siz[v] > n / 2) flag = false;
		siz[u] += siz[v];
	}
	if (flag && n - siz[u] <= n / 2)
		g[++sum] = u;
}

void init() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		edge[i].clear();
	for (int i = 1; i < n; i++) {
		ll u, v;
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
}

void dfs(int u, int fa) {
	bool flag = false;
	for (auto v : edge[u]) {
		if (v == fa) continue;
		dfs(v, u); flag = true;
	}
	if (flag == false) {
		ans = u;
	}
}

void solve() {
	sum = 0;
	find(1, 0);
	if (sum == 1) {
		for (auto v : edge[g[1]]) {
			cout << g[1] << " " << v << "\n";
			cout << g[1] << " " << v << "\n";
			return;
		}
	}
	dfs(g[1], g[2]);
	for (auto v : edge[ans]) {
		cout << ans << " " << v << "\n";
		cout << ans << " " << g[2] << "\n";
		return;
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		init();
		solve();
	}
	return 0;
}