[ARC117D]Miracle Tree

将$E_{i}$从小到大排序（显然不会相同），假设$E_{p_{i}}$为从小到大第$i$小

此时，必然有$E_{p_{1}}=1$，否则可以将$E_{p_{i}}$都减去$E_{p_{1}}-1$，之后即需要最小化$E_{p_{n}}$

当$p_{i}$确定后，题目中第2个条件即可变为$\forall 1\le i<j\le n,E_{p_{j}}-E_{p_{i}}\ge dist(p_{i},p_{j})$

取$j=i+1$时，即可推出$\forall 1\le i<n,E_{p_{i+1}}-E_{p_{i}}\ge dist(p_{i},p_{i+1})$

另一方面，此时即有$E_{p_{j}}-E_{p_{i}}=\sum_{k=i}^{j-1}E_{p_{k+1}}-E_{p_{k}}\ge \sum_{k=i}^{j-1}dist(p_{k},p_{k+1})\ge dist(p_{i},p_{j})$

（关于最后一个不等号，根据$dist(x,y)\le dist(x,z)+dist(z,y)$即可得到）

换言之，题目中第2个条件等价于$j=i+1$时的条件，那么$E_{p_{n}}$最小值即为$\sum_{i=1}^{n-1}dist(p_{i},p_{i+1})+1$

现在，问题即变为确定$p_{i}$，以最小化$E_{p_{n}}$（也即$\sum_{i=1}^{n-1}dist(p_{i},p_{i+1})+1$）

考虑将其补上$dist(p_{1},p_{n})$，此时考虑每一条边对答案的贡献，至少为2，且通过令$p_{i}$为dfs序来构造，可取到此下限，即和为$2(n-1)+1$

令$p_{1}$和$p_{n}$为树直径的两个端点，并以$p_{1}$为根优先搜索不包含$p_{n}$的子树即可构造出对应dfs序，令$d$为直径长度，则最终$E_{p_{n}}$即为$2(n-1)+1-d$

另外求$E_{i}$不需要求lca来求$dist(p_{i},p_{i+1})$，由于$\sum_{i=1}^{n-1}dist(p_{i},p_{i+1})$是$o(n)$的，直接在树上暴力移动，并判定其是否是后代即可

另外，题解中还提到了如何$o(n)$实现spj，只需要用桶排来对$p_{i}$排序，并以此判定相邻两者插值是否恰好为其距离即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 struct Edge{

 5     int nex,to;

 6 }edge[N<<1];

 7 int E,n,x,y,head[N],dfn[N],f[N],sz[N],dep[N],P[N],ans[N];

 8 bool check(int x,int y){

 9     return (dfn[x]<=dfn[y])&&(dfn[y]<dfn[x]+sz[x]);

10 }

11 void add(int x,int y){

12     edge[E].nex=head[x];

13     edge[E].to=y;

14     head[x]=E++;

15 }

16 int dis(int x,int y){

17     int ans=0;

18     while (!check(x,y)){

19         ans++;

20         x=f[x];

21     }

22     while (!check(y,x)){

23         ans++;

24         y=f[y];

25     }

26     return ans;

27 }

28 void dfs(int k,int fa,int s){

29     dfn[k]=++dfn[0];

30     f[k]=fa;

31     sz[k]=1;

32     dep[k]=s;

33     for(int i=head[k];i!=-1;i=edge[i].nex)

34         if (edge[i].to!=fa){

35             dfs(edge[i].to,k,s+1);

36             sz[k]+=sz[edge[i].to];

37         }

38 }

39 void construct(int k,int fa){

40     P[++P[0]]=k;

41     for(int i=head[k];i!=-1;i=edge[i].nex)

42         if ((edge[i].to!=fa)&&(!check(edge[i].to,y)))construct(edge[i].to,k);

43     for(int i=head[k];i!=-1;i=edge[i].nex)

44         if ((edge[i].to!=fa)&&(check(edge[i].to,y)))construct(edge[i].to,k);

45 }

46 int main(){

47     scanf("%d",&n);

48     memset(head,-1,sizeof(head));

49     for(int i=1;i<n;i++){

50         scanf("%d%d",&x,&y);

51         add(x,y);

52         add(y,x);

53     }

54     dfs(1,0,0);

55     x=y=1;

56     for(int i=2;i<=n;i++)

57         if (dep[x]<dep[i])x=i;

58     dfs(x,0,0);

59     for(int i=2;i<=n;i++)

60         if (dep[y]<dep[i])y=i;

61     construct(x,0);

62     ans[P[1]]=1;

63     for(int i=1;i<n;i++)ans[P[i+1]]=ans[P[i]]+dis(P[i],P[i+1]);

64     for(int i=1;i<=n;i++)printf("%d ",ans[i]);

65 }

巴特西

[ARC117D]Miracle Tree

最新文章

热门文章