松鼠的新家
尽管标签是省选/NOI-,但提交的通过率已经高到三分之一了。
但它仍旧是一个省选/NOI-的题。
大致题意就是按输入的顺序走一棵树,看每个节点经过多少次。问题就相当于把一条链上的所有节点权值都加一,最后统计每个点的权值。
但这样的时间复杂度比较高,所以我们可以把这条链的头节点和尾节点的权值都加一,然后把它们的LCA减一,它们LCA的父亲节点减一。之后每次通记每个节点都统计该节点及其子树的权值和,就是这个节点被经过的次数。
而题目要求在最后的终点不需要计算,所以我们可以把“这条链的头节点和尾节点的权值都加一”,改为“这条链的尾节点的父亲和头节点的权值都加一”,就可以实现题目要求。
#include<cstdio>
#include<iostream>
#define N 300010
using namespace std;
int next[N*],to[N*],num,head[N],ans[N],size[N],father[N],top[N],sum[N],n,a,b,c,deep[N],haha[N];
void add(int false_from,int false_to){
next[++num]=head[false_from];
to[num]=false_to;
head[false_from]=num;
}
void dfs1(int x){
size[x]=;
deep[x]=deep[father[x]]+;
for(int i=head[x];i;i=next[i])
if(father[x]!=to[i]){
father[to[i]]=x;
dfs1(to[i]);
size[x]+=size[to[i]];
}
}
void dfs2(int x){
int mmax=;
if(!top[x])
top[x]=x;
for(int i=head[x];i;i=next[i])
if(father[x]!=to[i]&&size[to[i]]>size[mmax])
mmax=to[i];
if(mmax){
top[mmax]=top[x];
dfs2(mmax);
}
for(int i=head[x];i;i=next[i])
if(father[x]!=to[i]&&to[i]!=mmax)
dfs2(to[i]);
}
void dfs3(int x){
ans[x]=sum[x];
for(int i=head[x];i;i=next[i])
if(father[x]!=to[i]){
dfs3(to[i]);
ans[x]+=ans[to[i]];
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])
swap(x,y);
x=father[top[x]];
}
if(deep[x]<deep[y])
return x;
return y;
}
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i)
scanf("%d",&haha[i]);
for(int i=;i<n;++i){
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs1();
dfs2();
for(int i=;i<n;++i){
a=haha[i];
b=haha[i+];
c=lca(a,b);
sum[a]++;
sum[father[b]]++;
sum[c]--;
sum[father[c]]--;
}
dfs3();
for(int i=;i<=n;++i)
printf("%d\n",ans[i]);
return ;
}