正题
题目链接:https://www.51nod.com/Contest/ProblemList.html#contestId=188&randomCode=291765
题目大意
n
n
n个点的一棵树，从
k
k
k节点出发，每次走到最远的一个节点(路上点最多,如果有多个就编号最小的)并将路上的点权变为0，求会依次到达哪些点。
解题思路
以
k
k
k为根，第一步直接走到深度最深的节点，但是第二步时我们发现起点变了。其实并不影响，因为路上的点权都变为了0，所以我们可以在来的路上瞎走，也就是可以直接回到起点而不影响答案。
那么问题就变为了每次修改路径点权后再找一条以
k
k
k开始的最长路径。我们对于每个节点点权修改后只会影响子树内，所以可以用
d
f
s
dfs
dfs序+线段树搞定。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std
;
const int N
=51000;
struct node
{
int to
,next
;
}a
[N
*2];
struct treenode
{
int l
,r
,w
,lazy
,num
;
};
int n
,k
,tot
,ls
[N
],dep
[N
],dfn
[N
],rfn
[N
],ed
[N
],fa
[N
],cnt
;
bool v
[N
];
struct LineTree
{
treenode t
[N
*4];
void Build(int x
,int l
,int r
)
{
t
[x
].l
=l
;t
[x
].r
=r
;
if(l
==r
){
t
[x
].w
=dep
[dfn
[l
]];
t
[x
].num
=dfn
[l
];
return;
}
int mid
=(l
+r
)/2;
Build(x
*2,l
,mid
);
Build(x
*2+1,mid
+1,r
);
if(t
[x
*2].w
>t
[x
*2+1].w
) t
[x
].num
=t
[x
*2].num
;
if(t
[x
*2].w
<t
[x
*2+1].w
) t
[x
].num
=t
[x
*2+1].num
;
if(t
[x
*2].w
==t
[x
*2+1].w
) t
[x
].num
=min(t
[x
*2].num
,t
[x
*2+1].num
);
t
[x
].w
=max(t
[x
*2].w
,t
[x
*2+1].w
);
}
void Downdata(int x
)
{
if(t
[x
].lazy
){
t
[x
*2].lazy
+=t
[x
].lazy
;
t
[x
*2+1].lazy
+=t
[x
].lazy
;
t
[x
*2].w
+=t
[x
].lazy
;
t
[x
*2+1].w
+=t
[x
].lazy
;
t
[x
].lazy
=0;
}
}
void Change(int x
,int l
,int r
,int num
)
{
if(t
[x
].l
==l
&&t
[x
].r
==r
){
t
[x
].w
+=num
;
t
[x
].lazy
+=num
;
return;
}
Downdata(x
);
int mid
=(t
[x
].l
+t
[x
].r
)/2;
if(r
<=mid
) Change(x
*2,l
,r
,num
);
else if(l
>mid
) Change(x
*2+1,l
,r
,num
);
else Change(x
*2,l
,mid
,num
),Change(x
*2+1,mid
+1,r
,num
);
if(t
[x
*2].w
>t
[x
*2+1].w
) t
[x
].num
=t
[x
*2].num
;
if(t
[x
*2].w
<t
[x
*2+1].w
) t
[x
].num
=t
[x
*2+1].num
;
if(t
[x
*2].w
==t
[x
*2+1].w
) t
[x
].num
=min(t
[x
*2].num
,t
[x
*2+1].num
);
t
[x
].w
=max(t
[x
*2].w
,t
[x
*2+1].w
);
}
}Tree
;
void addl(int x
,int y
)
{
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;
}
void dp(int x
)
{
rfn
[x
]=++cnt
;dfn
[cnt
]=x
;
for(int i
=ls
[x
];i
;i
=a
[i
].next
){
int y
=a
[i
].to
;
if(y
==fa
[x
]) continue;
dep
[y
]=dep
[x
]+1;
fa
[y
]=x
;dp(y
);
}
ed
[x
]=cnt
;
}
int main()
{
scanf("%d%d",&n
,&k
);k
++;
for(int i
=2;i
<=n
;i
++){
int x
;scanf("%d",&x
);
addl(i
,x
+1);addl(x
+1,i
);
}
dep
[k
]=1;dp(k
);
Tree
.Build(1,1,n
);
printf("%d\n",k
-1);
while(Tree
.t
[1].w
){
int x
=Tree
.t
[1].num
;
printf("%d\n",x
-1);
while(x
&&!v
[x
]){
Tree
.Change(1,rfn
[x
],ed
[x
],-1);
v
[x
]=1;x
=fa
[x
];
}
}
}
