CF1009F Dominant Indices

CodeForces

Luogu翻译

分析

考虑一个$O(n^2)$的DP。

设$f[i][j]$表示以$i$为根的子树内到$i$的距离为$j$的点的个数。

$\large f[i][j]=\sum f[son][j-1]$

发现这个方程极其眼熟(雾)。

还是假设只有一个儿子,方程变为$\large f[i][j]=f[son][j-1]$

写成指针形式:$f[i]=f[son]-1$

然后就可以上长链剖分了。dfs的时候顺便把答案搞出来就行。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000000+10;

struct Edge { int v,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v){
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}

int n;
int height[MAXN],hson[MAXN],dep[MAXN];
int *f[MAXN],tmp[MAXN<<1],*id=tmp;
int ans[MAXN];

inline void dfs1(int u,int fa) {
    height[u]=dep[u]=dep[fa]+1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs1(v,u); height[u]=max(height[v],height[u]);
        if (!hson[u]||height[v]>height[hson[u]]) hson[u]=v;
    }
}

inline void dfs(int u,int fa) {
    f[u][0]=1;
    if (hson[u])
        f[hson[u]]=f[u]+1,dfs(hson[u],u),ans[u]=ans[hson[u]]+1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa||v==hson[u]) continue;
        f[v]=id,id+=height[v]-dep[v]+1; dfs(v,u);
        for (re int j=0;j<=height[v]-dep[v];++j) {
            f[u][j+1]+=f[v][j];
            if (f[u][j+1]>f[u][ans[u]]||(f[u][j+1]==f[u][ans[u]]&&ans[u]>j+1))
                ans[u]=j+1;
        }
    }
    if (f[u][ans[u]]==1) ans[u]=0;
}

int main() {
    n=read();
    for (re int i=1,u,v;i<n;++i) {
        u=read(),v=read();
        addEdge(u,v); addEdge(v,u);
    }
    dfs1(1,0);
    f[1]=id,id+=height[1]; dfs(1,0);
    for (re int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}
最后修改:2019 年 09 月 24 日 09 : 00 PM

发表评论