[NC记录]ARC117D Miracle Tree

**题意** ： 给出一棵 $n$ 个节点的树，要求给每个节点赋予权值 $c_u$ ，满足下列条件。 - $1\leq c_u$ - 对于点 $u,v$ ，$|c_u-c_v|\geq dis(u,v)$。 - 满足上述两个条件的情况下，$c_u$ 的最大值最小。 构造一种方案。 $n\leq 2\times 10^5$ ，时限$\texttt{2s}$。 ------------ - **性质** ： 将点按照 $c$ 从大到小排序为 $p_1,p_2,...p_n$ ，则第二条要求可以改写为 ： $$dis(p_i,p_{i+1})\leq c_{p_{i+1}}-c_{p_i}$$ 因为对于 $i<j<k$ 有 $dis(p_i,p_k)\leq dis(p_i,p_j)+dis(p_j,p_k)\leq c_{p_k}-c_{p_j}+c_{p_j}-c_{p_i}=c_{p_k}-c_{p_i}$ ，所以能确保其他点对成立。 对于一个给定的 $p$ ，为了使得 $c$ 的最大值最小，我们令 $c_{p_{i+1}}-c_{p_i}=dis(p_i,p_{i+1})$ $c$ 中的最大值即为 $1+\sum\limits_{i=1}^{n-1}dis(p_i,p_{i+1})$ 问题转化为 ： 找一个排列 $p$ ，使得 $\sum\limits_{i=1}^{n-1}dis(p_i,p_{i+1})$ 最小。 若在树上走一个环路，则长度为 $2(n-1)$ 。 选取直径端点作为起点和终点，若直径长度为 $len$ （点数）则长度为 $2n-len-1$。 - **另一种思路** 首先不难想到用欧拉序中的 $in$ 来作为 $c$。 （根据树上莫队的正确性）该构造显然合法，但不一定最优。 考虑从直径的某一段开始 $\rm dfs$ ，而从另一端结束，这样能使得最大的 $in$ 最小。 具体地，若直径长度为 $len$ （点数） ，最大的 $in$ 为 $2n-len$。 复杂度 $O(n)$。 ```cpp #include<algorithm> #include<cstdio> #define pb push_back #define MaxN 200500 using namespace std; vector<int> g[MaxN]; int dep[MaxN]; void dfs1(int u) { for (int i=0,v;i<g[u].size();i++) if (!dep[v=g[u][i]]){ dep[v]=dep[u]+1; dfs1(v); } } int len[MaxN],mp[MaxN]; void dfs2(int u,int fa) { len[u]=0; for (int i=0,v;i<g[u].size();i++) if ((v=g[u][i])!=fa){ dfs2(v,u); len[u]=max(len[u],len[v]+1); if (len[v]>len[mp[u]]) mp[u]=v; } } int dfn[MaxN],tim; void dfs3(int u,int fa) { dfn[u]=++tim; for (int i=0;i<g[u].size();i++) if (g[u][i]!=fa&&g[u][i]!=mp[u]) dfs3(g[u][i],u); if (mp[u])dfs3(mp[u],u); tim++; } int n; int main() { scanf("%d",&n); for (int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); g[u].pb(v);g[v].pb(u); } dep[1]=1;dfs1(1); int rt=0; for (int i=1;i<=n;i++) if (dep[i]>dep[rt])rt=i; dfs2(rt,0); dfs3(rt,0); for (int i=1;i<=n;i++) printf("%d ",dfn[i]); return 0; } ```