bruh

prog3r

May 5th, 2025

206

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 3.71 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LO
#pragma GCC optimize("trapv")
#endif
constexpr int MOD = (119<<23)+1;
//constexpr int MOD = 1e9+7;
signed main() {
#ifndef LO
clog << "FIO\n";
ios::sync_with_stdio(0);
cin.tie(0);
#endif
int TT = 1;
cin >> TT;
for (int tt = 0; tt < TT; tt += 1) {
int n;
cin >> n;
vector<vector<int>> adj(n+1);
for (int i = 0; i < n-1; i += 1) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<tuple<int,int,int>> ans;
vector<bool> noapple(n+1);
auto get_down = [&] (auto f, const int root) -> void {
queue<int> q;
map<int,int> dist;
dist[root] = 0;
q.push(root);
int max_dist = 0;
int max_dist_vert = root;
while (!q.empty()) {
auto tp = q.front();
q.pop();
for (const auto &x : adj[tp]) if (!noapple[x]) {
if (!dist.count(x) || dist[x] > dist[tp] + 1) {
dist[x] = dist[tp] + 1;
q.push(x);
if (max_dist < dist[x] || max_dist == dist[x] && x > max_dist_vert) {
max_dist_vert = x;
max_dist = dist[x];
}
}
}
}
int from = max_dist_vert;
dist.clear();
dist[from] = 0;
q.push(from);
max_dist = 0;
max_dist_vert = from;
while (!q.empty()) {
auto tp = q.front();
q.pop();
for (const auto &x : adj[tp]) if (!noapple[x]) {
if (!dist.count(x) || dist[x] > dist[tp] + 1) {
dist[x] = dist[tp] + 1;
q.push(x);
if (max_dist < dist[x] || max_dist == dist[x] && x > max_dist_vert) {
max_dist_vert = x;
max_dist = dist[x];
}
}
}
}
int to = max_dist_vert;
set<int> seen;
bool done = false;
vector<int> stack;
auto dfs = [&] (auto f, int u) -> void {
stack.push_back(u);
if (u == to) {
done = true;
return;
}
for (const auto &x : adj[u]) if (!noapple[x]) {
if (!seen.count(x)) {
seen.insert(x);
f(f, x);
}
if (done) {
return;
}
}
stack.pop_back();
};
seen.insert(from);
dfs(dfs, from);
vector<int> nw;
for (const auto &x : stack) {
noapple[x] = true;
}
for (const auto &x : stack) {
for (const auto &v : adj[x]) {
if (!noapple[v]) {
nw.push_back(v);
}
}
}
ans.push_back({stack.size(), max(from, to), min(from, to)});
for (const auto &v : nw) {
f(f, v);
}
};
get_down(get_down, 1);
sort(ans.rbegin(), ans.rend());
for (const auto &[_1, _2, _3] : ans) {
cout << _1 << " " << _2 << " " << _3 << " ";
}cout << "\n";
}
}

Add Comment

Please, Sign In to add comment