长链剖分板子题啊
长链剖分有几个神奇的性质
-
所有长链的总点数为(n)
-
任意一个点的(k)级祖先所在长链的长度肯定不小于(k)
-
从任意点到根经过的短边数量不超过(sqrt{n})，也就是用长链剖分求(LCA)是根号复杂度的。。
最后一个性质是这样的，从一个点往上经过一条短边，点数要加(1)，再经过一条短边，点数要加(2)，经过一共(k)条短边，点数要加(frac{k(k+1)}{2})，于是短边次数就是(sqrt{n})级别的
之后长链剖分可以(O(1))求(k)级祖先，不过好像没什么用啊，最主要的作用还是用来优化一些树上跟深度有关系的转移，可以做到均摊(O(n))复杂度
比如说这道题我们设(f[x][j])表示在(x)的子树中距离(x)深度为(j)的点有多少个
我们需要另(x)直接继承其长儿子的状态，就是(f[x][j+1]=f[son[x]][j])，这个需要用指针(O(1))实现
之后对于所有的短儿子，我们直接暴力合并过去
我们发现这样之后在一个点不是其父亲的长儿子的时候会暴力合并，代价是这条长链的长度，根据性质(1)，所有长链的长度为(n)，所以这个算法是均摊(O(n))的
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=1000005;
inline int read() {
char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt;}e[maxn<<1];
int head[maxn],deep[maxn],len[maxn],son[maxn];
int n,num,tax[maxn],*id=tax,*f[maxn],ans[maxn];
inline void add(int x,int y) {
e[++num].v=y;e[num].nxt=head[x];head[x]=num;
}
void dfs1(int x) {
int maxx=-1;
for(re int i=head[x];i;i=e[i].nxt) {
if(deep[e[i].v]) continue;
deep[e[i].v]=deep[x]+1;
dfs1(e[i].v);
if(len[e[i].v]>maxx) maxx=len[e[i].v],son[x]=e[i].v;
}
len[x]=len[son[x]]+1;
}
void dfs(int x) {
f[x][0]=1;
if(son[x]) f[son[x]]=f[x]+1,dfs(son[x]),ans[x]=ans[son[x]]+1;
for(re int i=head[x];i;i=e[i].nxt) {
if(deep[e[i].v]<deep[x]||e[i].v==son[x]) continue;
f[e[i].v]=id;id+=len[e[i].v];dfs(e[i].v);
for(re int j=1;j<=len[e[i].v];j++) {
f[x][j]+=f[e[i].v][j-1];
if(f[x][j]>f[x][ans[x]]||(f[x][j]==f[x][ans[x]]&&j<ans[x]))
ans[x]=j;
}
}
if(f[x][ans[x]]==1) ans[x]=0;
}
int main() {
n=read();
for(re int x,y,i=1;i<n;i++)
x=read(),y=read(),add(x,y),add(y,x);
deep[1]=1,dfs1(1);
f[1]=id,id+=len[1];dfs(1);
for(re int i=1;i<=n;i++) printf("%d
",ans[i]);
return 0;
}