求助DSU on tree

_Seniorious_ @ 2022-04-01 21:27:44

#include <bits/stdc++.h>
using namespace std;
int d[1000005],sz[1000005],big[1000005],cnt[1000005],ans[1000005],n,res=0;
vector<int> nodes[1000005];
void add(int de)
{
    cnt[de]++;
    if(cnt[de]>cnt[res]||(cnt[de]==cnt[res]&&de<res))res=de;
    return;
}
void del(int de)
{
    cnt[de]--;
    return;
}
void dfs2(int u,int fa,bool keep)
{
    if(keep)add(d[u]);
    else del(d[u]);
    for(int v:nodes[u])if(v!=fa)dfs2(v,u,keep);
    return;
}
void dfs1(int u,int fa)
{
    for(int v:nodes[u])
    {
        if(v==fa||v==big[u])continue;
        dfs1(v,u);
        dfs2(v,u,false);
        res=0;
    }
    if(big[u])dfs1(big[u],u);
    for(int v:nodes[u])if(v!=fa&&v!=big[u])dfs2(v,u,true);
    add(d[u]);
    ans[u]=res-d[u];
    return;
}
void dfs0(int u,int fa)
{
    sz[u]=1,d[u]=d[fa]+1;
    for(int v:nodes[u])if(v!=fa)dfs0(v,u);
    if(sz[u]>sz[big[fa]])big[fa]=u;
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        nodes[u].push_back(v);
        nodes[v].push_back(u);
    }
    dfs0(1,0);
    dfs1(1,0);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

by _Seniorious_ @ 2022-04-01 21:28:17

p.s. 用链式前向星存图也没有用

by Neutralized @ 2022-04-02 16:06:16

前向星常数本来就应该比较大吧？

by Neutralized @ 2022-04-03 09:07:02

呃，昨天没时间写这个题了
今天写了一下
这是没有刻意卡常的实现，1.8min
您可以参考一下

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define ri register int
#define ll long long

#define Tp template<class T>
#define isd(x) (x>=48&&x<=57)
#define g() getchar()
#define pc(x) putchar(x)
namespace SlowIO{
    Tp inline void rd(T &x) {
        x=0; char i=g(); bool f=1;
        while(!isd(i)) f&=(i!='-'),i=g();
        while(isd(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
        x*=((f<<1)-1);
    }
    const int OUT=1e6;
    static char st[OUT]; int out;
    Tp inline void op(T x){
        out=0; x<0&&(x=-x,pc('-'));
        if(!x){ pc(48); return; }
        while(x) st[++out]=x%10+48,x/=10;
        while(out) pc(st[out--]);
    }
    Tp inline void writeln(T x){ op(x);pc('\n'); }
    Tp inline void writesp(T x){ op(x); pc(' '); }
    Tp inline void write(T x,char c=0){ op(x); c&&pc(c); }
}; using namespace SlowIO;

#define N 1000001
//统计u子树中到根节点深度为x的点
//然后选最小减掉u的深度即可
//DSU On Tree!
int n;
int head[N],cntr;
struct edge{
    int to,nxt;
}e[N<<1];
inline void add(int u,int v){
    e[++cntr]=(edge){v,head[u]};
    head[u]=cntr;
}
#define gfore(u) for(ri i=head[u];i;i=e[i].nxt)

int depth[N],son[N];
int siz[N],fa[N];
int cnt[N],res;
int ans[N];
inline void dfs(int u,int father){
    depth[u]=depth[father]+1;
    fa[u]=father,siz[u]=1;
    gfore(u){ int &v=e[i].to;
        if(v==father) continue;
        dfs(v,u),siz[u]+=siz[v];
        son[u]=(siz[son[u]]<siz[v]?v:son[u]);
    }
}
inline void calc(int u,int delta){
    cnt[depth[u]]+=delta;
    if(cnt[depth[u]]>cnt[res]) res=depth[u];
    if(cnt[depth[u]]==cnt[res]&&res>depth[u]) res=depth[u];
    gfore(u){ int &v=e[i].to;
        if(v==fa[u]) continue;
        calc(v,delta);
    }
}
inline void mau5(int u,int f){
    gfore(u){ int &v=e[i].to;
        if(v==son[u]||v==fa[u]) continue;
        mau5(v,0);
    } if(son[u]) mau5(son[u],1);
    ++cnt[depth[u]];
    if(cnt[depth[u]]>cnt[res]) res=depth[u];
    if(cnt[depth[u]]==cnt[res]&&res>depth[u]) res=depth[u];
    gfore(u){ int &v=e[i].to;
        if(v==son[u]||v==fa[u]) continue;
        calc(v,1);
    } ans[u]=res-depth[u];
    if(!f) calc(u,-1),res=0;
}

int main()
{
    rd(n);
    for(ri i=1,u,v;i<=n-1;++i){
        rd(u),rd(v);
        add(u,v),add(v,u);
    } dfs(1,0),mau5(1,1);
    for(ri i=1;i<=n;++i)
    writeln(ans[i]);
    return 0;
}