ARC 117 - Miracle Tree

话说我只能蒙结论。。。

打表或者理性分析可以发现一些性质

1.$\nexists E_i=E_j$

2.如果确定$E_i$从小到大的顺序$P_i$，就能确定一组最优的$E_i$

（但是对于平凡的$P_i$，这个过程会极其恶心，因此考虑特殊化$P_i$）

3.设$\displaystyle f(P)=\sum_{i=2}^n dis(P_{i-1},P_i)$，即遍历排列的距离和

则$\max\{E_i\}\ge \min\{f(P)\}+1$

显然

由此确定了一个下界，接下来将说明可以取到下界

1.对于一个排列$P_{i}$，如果$P_i$是一组$\text{dfs}$序，那么满足$\max\{E_i\}=f(P)+1$ (容易模拟发现)

2.$\min\{f(P)\}$在$(P_1,P_n)$恰好为一条直径时取到，显然存在这样一组$\text{dfs}$序满足要求

由此确定了答案$P$可以是任何一组以某一条直径两个端点为$P_1,P_n$的$\text{dfs}$序

容易给出一个合法解，代码实现极为暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int N=2e5+10,INF=1e9+10;

int n;
vector <int> G[N];
int F[N][20],D[N],E[N];
int ma=-1,id;
void dfs(int u,int f) {
	if(D[u]>ma) ma=D[u],id=u;
	F[u][0]=f,E[u]=D[u];
	rep(i,1,18) F[u][i]=F[F[u][i-1]][i-1];
	for(int v:G[u]) if(v!=f) D[v]=D[u]+1,dfs(v,u),cmax(E[u],E[v]);
	sort(G[u].begin(),G[u].end(),[&](int x,int y){ return E[x]<E[y]; });
}
int LCA(int x,int y){
	if(D[x]<D[y]) swap(x,y);
	for(int del=D[x]-D[y],i=0;(1<<i)<=del;++i) if(del&(1<<i)) x=F[x][i];
	if(x==y) return x;
	drep(i,18,0) if(F[x][i]!=F[y][i]) x=F[x][i],y=F[y][i];
	return F[x][0];
}
int Dis(int x,int y){ return D[x]+D[y]-2*D[LCA(x,y)]; }

int lst;
ll A[N];
void dfs2(int u,int f) {
	if(!lst) A[lst=u]=1;
	else A[u]=A[lst]+Dis(lst,u),lst=u;
	for(int v:G[u]) if(v!=f) dfs2(v,u);
}

int main(){
	n=rd();
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),G[v].pb(u);
	}
	dfs(1,0);
	int u=id;
	dfs(u,0),dfs2(u,0);
	rep(i,1,n) printf("%lld ",A[i]);
}