题解 CF1009F 【Dominant Indices】

feecle6418 · 2020-03-11 16:06:20 · 题解

线段树合并。

普通的线段树合并空间是 O(n\log n)，容易被卡空间、其实利用垃圾回收可以做到线性。

由于在任意时刻，有用的只有深度为 i 的和深度为 i+1 的点的线段树，我们可以在合并完成后将不用的点重复利用，开一个栈来记录废弃的点即可。

代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n,cnt,cntt,h[1000005],root[1000005],ans[1000005];
int st[4000005],top;
struct TreeNode{
    int ls,rs,maxx,maxp;
    void Clear(){
        ls=rs=maxx=maxp=0;
    }
}t[4000005];
struct Edge{
    int to,next;
}e[2000005];
struct Que{
    int k,id;
};
int NewNode(){
    if(top)return st[top--];
    return ++cntt;
}
void Add_Edge(int x,int y){
    e[++cnt].to=y;
    e[cnt].next=h[x];
    h[x]=cnt;
}
void Pushup(int p){
    int l=t[p].ls,r=t[p].rs;
    if(t[l].maxx==t[r].maxx){
        t[p].maxx=t[l].maxx,t[p].maxp=t[l].maxp;
        return ;
    }
    if(t[l].maxx>t[r].maxx){
        t[p].maxx=t[l].maxx,t[p].maxp=t[l].maxp;
    }
    else {
        t[p].maxx=t[r].maxx,t[p].maxp=t[r].maxp;
    }
}
void Update(int &p,int l,int r,int x){
    if(!p)p=NewNode();
    if(l==r){
        t[p].maxx++,t[p].maxp=l;
        return ;
    }
    int mid=(l+r)/2;
    if(x<=mid)Update(t[p].ls,l,mid,x);
    else Update(t[p].rs,mid+1,r,x);
    Pushup(p);
}
void Merge(int &p,int q,int l,int r){
    if(!p||!q){
        p=p+q;
        return ;
    }
    if(l==r){
        t[p].maxx+=t[q].maxx;
        t[q].Clear(),st[++top]=q;
        return ;
    }
    int mid=(l+r)/2;
    Merge(t[p].ls,t[q].ls,l,mid);
    Merge(t[p].rs,t[q].rs,mid+1,r);
    Pushup(p);
    t[q].Clear(),st[++top]=q;
}
void Solve(int now,int fa,int dep){
    root[now]=++cntt;
    for(int i=h[now];i;i=e[i].next){
        int y=e[i].to;
        if(y==fa)continue;
        Solve(y,now,dep+1);
        Merge(root[now],root[y],1,n);
    }
    Update(root[now],1,n,dep);
    ans[now]=t[root[now]].maxp-dep;
}
int main(){
    scanf("%d",&n);
    for(int i=2,x,y;i<=n;i++){
        scanf("%d%d",&x,&y);
        Add_Edge(x,y);
        Add_Edge(y,x);
    }
    Solve(1,0,1);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}