题解

· · 题解

发一个 O(n) 的题解。

问题可以看作对于每一个 x，计算它对哪些 y 有贡献。

令 z=lca(x,y)。

首先，在 x 到 z 之前一定不会到 y，故可以把问题转化到 z 上，视为 z 已被选。

此时，y 能被选当且仅当 y 到 z 的路径最大值（包括 y 不包括 z）小于 z 到根的路径最大值（不包括 z 也不包括根），因为到根之前必定会经过这些点，而若其中的最大值是下一个，则一定先会走到 y 所在的子树。

进一步考虑，若 z 的父亲合法，则 z 一定合法，因为下半部分的路径最大值只会减小，上半部分的路径最大值只会增加，所以说，我们只用找到深度最小的 z 即可。

这个东西很好直接用数据结构维护，但由于有些麻烦，且题目中还有未利用的条件，这里继续介绍 O(n) 的做法。

对于每一个点 y，观察它到根的路径最大值 A，若 z 选取在 A 的下方，则上方一定大于下方，若 z 选取在 A 的上方，则下方一定大于上方。

唯一的问题就是 A 这个位置能否被选。

记录一下路径次大值，判断在 A 上方还是下方即可。

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
    re int t=0;re char v=getchar();
    while(v<'0')v=getchar();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return t;
}
int n,head[200002],dfn[200002],c[200002],cnt,siz[200002],a[200002],tim,b[200002],v[200002],fr[200002];
struct edge{int to,next;}e[400002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
inline void dfs(re int x,re int y){
    dfn[x]=++tim,a[x]=a[y],b[x]=b[y],siz[x]=1;
    if(x>a[x])b[x]=a[x],a[x]=x,fr[x]=x;
    else if(x>b[x])b[x]=x;
    if(dfn[b[x]]>dfn[a[x]])++v[fr[x]];
    else ++v[a[x]];
    for(re int i=head[x];i;i=e[i].next)
        if(e[i].to^y)fr[e[i].to]=(a[x]==x?e[i].to:fr[x]),dfs(e[i].to,x),siz[x]+=siz[e[i].to];
}
int main(){
    n=read();
    for(re int i=1,x,y;i<n;++i)x=read(),y=read(),add(x,y),add(y,x);
    dfs(1,1);
    for(re int i=2;i<=n;++i)c[dfn[i]]+=v[i],c[dfn[i]+siz[i]]-=v[i];
    for(re int i=2;i<=n;++i)c[i]+=c[i-1];
    for(re int i=2;i<=n;++i)printf("%d ",c[dfn[i]]);
}