ARC117 D

ARC117 D

题意：

解法：

先画画图：

右边是6的原因是，要满足6位置的点和3位置的点距离>=3。

从这里可以发现，如果存在多个子链，那么下一条子链的第一个权值=上一条子链最后一个权值+回溯链长。

为了使得回溯链长总和最小，容易想到将最长的链放到最后赋值。

具体做法是先找到树的直径，然后从直径的一端点开始赋值，先对非直径赋值，再对直径赋值，
回溯的时候赋值用的tot++，因为要加上回溯链长。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxm=2e6+5;
vector<int>g[maxm];
int dep[maxm],son[maxm];
int ans[maxm];
int n;
void dfs1(int x,int fa){dep[x]=dep[fa]+1;for(int v:g[x]){if(v==fa)continue;dfs1(v,x);}
}
void dfs2(int x,int fa){dep[x]=0;for(int v:g[x]){if(v==fa)continue;dfs2(v,x);dep[x]=max(dep[x],dep[v]+1);if(dep[v]>dep[son[x]]){son[x]=v;}}
}
int tot=0;
void dfs3(int x,int fa){ans[x]=++tot;for(int v:g[x]){if(v==fa||v==son[x])continue;dfs3(v,x);}if(son[x]){dfs3(son[x],x);}tot++;//回溯的时候要加上回溯链的长度.
}
void solve(){cin>>n;for(int i=1;i<n;i++){int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}//找直径的一端dfs1(1,1);int ma=1;for(int i=1;i<=n;i++){if(dep[i]>dep[ma]){ma=i;}}dfs2(ma,ma);//计算长短儿子//dfs3(ma,ma);//计算答案//for(int i=1;i<=n;i++){cout<<ans[i]<<' ';}cout<<endl;
}
signed main(){ios::sync_with_stdio(0);solve();return 0;
}