\(\text{Problem}:\)[ARC117D] Miracle Tree
\(\text{Solution}:\)
考虑 \(\lvert E_{i}-E_{j}\rvert \geq dist(i,j)\) 的意义，令 \(E_{i}<E_{j}\)，即在树上选择一条 \(i\rightarrow j\) 的长度为 \(l\) 的路径，使得 \(E_{j}=E_{i}+l\)。
那么问题转化为：从树上任意一点开始，经过最少的边数遍历所有点。
不难发现，每条边最多被遍历两次。让只被遍历一次的边最多，只需找出树的直径，最后走这条链即可。总时间复杂度 \(O(n)\)。
\(\text{Code}:\)
#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=200010;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘) s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,root,mxd,mxp,book[N],f[N],ans[N],cnt;
int head[N],maxE; struct Edge { int nxt,to; }e[N<<1];
inline void Add(int u,int v) { e[++maxE].nxt=head[u]; head[u]=maxE; e[maxE].to=v; }
void DFS1(int x,int fa,int dep)
{
if(dep>=mxd) mxd=dep, root=x;
for(ri int i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa) continue;
DFS1(v,x,dep+1);
}
}
void DFS2(int x,int fa,int dep)
{
if(dep>=mxd) mxd=dep, mxp=x;
for(ri int i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa) continue;
f[v]=x;
DFS2(v,x,dep+1);
}
}
void DFS3(int x,int fa)
{
ans[x]=++cnt;
for(ri int i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa||book[v]) continue;
DFS3(v,x), cnt++;
}
for(ri int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa&&book[e[i].to]) DFS3(e[i].to,x), cnt++;
}
signed main()
{
n=read();
for(ri int i=1;i<n;i++)
{
int u,v;
u=read(), v=read();
Add(u,v), Add(v,u);
}
DFS1(1,0,0), mxd=0;
DFS2(root,0,0);
while(mxp!=root) book[mxp]=1, mxp=f[mxp];
DFS3(root,0);
for(ri int i=1;i<=n;i++) printf("%d ",ans[i]); puts("");
return 0;
}