CF-1023-D. Apple Tree Traversing · znzryb
## 思路讲解
题意就是所有点只能经过一次（选择一次），构造出字典序最大的 $(dis,u,v)$ 序列，输出这个序列。
注意到，距离是放在第一位的，所以我们肯定优先选择距离最大的。那在树上路径距离最大的是什么？树的直径呗。不过这个树的直径的取法需要优先选择大的起始点和终止点。
然后删除直径后，这张图就不联通了，只要在每个子图中我们遵循这种删除规律即可，最后形成的 ans 数组根据字典序规则排序即可。
以下是样例五的图示展示，第一层删完后，变为了两个子图，这两个子图仍然按照规则选择直径，删除直径上的点，整张图被删完后程序结束。
## 时间复杂度分析
枚举总量为 $n+(n-l_1)+(n-l_1-l_2)+\cdots+(n-l_c-\cdots-l_i-\cdots l_1)$，即 $n\times c -l_1 \times c-l_2 \times (c-1)-\cdots-l_c$，也就是，其中 $n$ 为点的数量，$l_i$ 为第 i 层的直径总数，c 为总层数。枚举总量在逐层下降是因为每层选择的直径上的点会被删除。
n 是给定的，那么我们假设 c 最大，那么 c 最大的情况是什么呢？
c 最大的情况，就是我们每层只能删除一条直径，也就是说该图在删除直径的过程中一直保持着联通状态。把层数卡满的图可以这样构造，注意到，$分枝直径的点的数量≤\lfloor直径的点的数量/2\rfloor$，如果大于这个限制，该分枝就要被删除了。
那么近似的，我们可以得到。
$$
x+\frac{x}{2}+\frac{x}{2^2}+\cdots+\frac{x}{2^c}=n
$$
由于$\lfloor\frac{x}{2^c}\rfloor$必须大于 $0$，我们知道 $2^c≤x<2^{c+1}$。
那么不妨令 $x=2^{c+1}$。
$$
2^{c+1}+2^c+\cdots+2=n
$$
运用等比数列求和公式。
$$
2\times(2^{c+1}-1)=n
$$
因此，$c\approx \log(n)$。
故该算法的总体时间复杂度为$O(nlogn)$。
## AC代码
[https://codeforces.com/contest/2107/submission/318737306](https://codeforces.com/contest/2107/submission/318737306)
::: 源代码
```cpp
// Problem: D. Apple Tree Traversing
// Contest: Codeforces - Codeforces Round 1023 (Div. 2)
// URL: https://codeforces.com/contest/2107/problem/D
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define deShow(var) cerr << #var <<":";
#define DEBUG(variable) \
do { \
std::cerr << #variable << ":"; \
for (const auto& elem : variable) { \
std::cerr << elem << " "; \
} \
std::cerr << "\n"; \
} while (0)
#define uniVec(var) \
do { \
sort(var.begin(),var.end());\
var.resize(unique(var.begin(),var.end())-var.begin());\
} while (0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,K,T;
vector<ll> g[MAXN];
bool vis[MAXN]/*,isVal[MAXN]*/;
vector<arr> disNode;
vector<ll> needDel;
ll st,ed,d;
set<ll> nodes;
bool removed[MAXN];
void dfs(ll x,ll d){
disNode.pb({d,x});
vis[x]=true;
FOR(i,0,SZ(g[x])-1){
ll node=g[x][i];
if(vis[node]) continue;
if(removed[node]) continue;
dfs(node,d+1);
}
}
bool dfsDia(ll x){ // 一个比较简单的树上dp？
vis[x]=true;
if(x==ed){
needDel.pb(ed);
return true;
}
bool rec=false;
FOR(i,0,SZ(g[x])-1){
ll node=g[x][i];
if(vis[node]) continue;
if(removed[node]) continue;
rec|=dfsDia(node);
}
if(rec) needDel.pb(x);
return rec;
}
inline void init(){
disNode.clear(),needDel.clear();
FOR(i,1,N){
vis[i]=false;
}
}
inline bool cmp(const array<ll,3> &a,const array<ll,3> &b){
if(a[0]!=b[0]) return a[0]>b[0];
if(a[1]!=b[1]) return a[1]>b[1];
return a[2]>b[2];
}
inline void solve(){
cin>>N;
// 所有点只能经过一次（选择一次）
// 构造出字典序最大的(d,u,v)序列，输出这个序列
// d要大，u要大，v要大
disNode.clear(),needDel.clear(),nodes.clear();
FOR(i,1,N){
vis[i]=false;
nodes.insert(i);
g[i].clear();
removed[i]=false;
}
FOR(i,1,N-1){
ll u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
if(N==1){ // 特判
cout<<"1 1 1\n";
return;
}
dfs(1,0);
sort(all(disNode));
#ifdef LOCAL
deShow(disNode)
FOR(i,0,SZ(disNode)-1){
cerr<<disNode[i][0]<<" "<<disNode[i][1]<<"\n";
}
#endif
st=disNode.back()[1];
init();
dfs(st,0);
sort(all(disNode));
ed=disNode.back()[1];
d=disNode.back()[0];
init();
dfsDia(st);
vector<array<ll,3>> ans;
ans.pb({d+1,max(st,ed),min(st,ed)});
for(const auto &node:needDel){
nodes.erase(node);
removed[node]=true;
}
for(const auto &node:nodes){
vis[node]=false;
}
while(!nodes.empty()){
disNode.clear(),needDel.clear();
dfs(*nodes.begin(),0);
sort(all(disNode));
st=disNode.back()[1];
FOR(i,0,SZ(disNode)-1){
vis[disNode[i][1]]=false;
}
disNode.clear(),needDel.clear();
dfs(st,0);
sort(all(disNode));
ed=disNode.back()[1];
d=disNode.back()[0];
ans.pb({d+1,max(st,ed),min(st,ed)});
FOR(i,0,SZ(disNode)-1){
vis[disNode[i][1]]=false;
}
dfsDia(st);
FOR(i,0,SZ(disNode)-1){
vis[disNode[i][1]]=false;
}
for(const auto &node:needDel){
nodes.erase(node);
removed[node]=true;
}
}
sort(all(ans),cmp);
FOR(i,0,SZ(ans)-1){
cout<<ans[i][0]<<" "<<ans[i][1]<<" "<<ans[i][2]<<" ";
}
cout<<"\n";
#ifdef LOCAL
DEBUG(needDel);
cerr<<"\n";
#endif
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
// solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2107/submission/318737306
*/
```
:::
## 心路历程（WA，TLE，MLE……）