ARC 117 - Miracle Tree

Posted on Edited on In

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\) (容易模拟发现)

  1. \(\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]);
}