生活随笔
收集整理的這篇文章主要介紹了
长链剖分
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
長(zhǎng)鏈剖分也屬于樹鏈剖分的一種
一般講的樹剖都指輕重鏈剖分，它可以用于維護(hù)樹上路徑的信息
而長(zhǎng)鏈剖分則是用于維護(hù)有關(guān)深度的信息
剖分方法
長(zhǎng)鏈剖分的剖分方法與輕重鏈剖分極其相似
只需要把以子樹大小判斷重兒子改成以節(jié)點(diǎn)深度判斷即可
void dfs1(int u
,int pa
)
{dep
[u
]=mxd
[u
]=dep
[pa
]+1;for(int i
=head
[u
];i
;i
=E
[i
].nxt
){int v
=E
[i
].v
;if(v
==pa
) continue;dfs1(v
,u
);if(mxd
[v
]>mxd
[u
]) mxd
[u
]=mxd
[v
],son
[u
]=v
; }
}void dfs2(int u
,int tp
)
{top
[u
]=tp
;if(son
[u
]) dfs2(son
[u
],tp
);for(int i
=head
[u
];i
;i
=E
[i
].nxt
){int v
=E
[i
].v
;if(v
==son
[u
]||v
==fa
[u
][0]) continue;dfs2(v
,v
);}
}
長(zhǎng)鏈剖分性質(zhì)
性質(zhì)1：長(zhǎng)鏈剖分后，所有節(jié)點(diǎn)都僅屬于一條鏈
性質(zhì)2：任意節(jié)點(diǎn)u的第k級(jí)祖先v所在鏈的長(zhǎng)度一定大于k
證明：
若u,v在一條鏈上，那么顯然鏈長(zhǎng)大于k
若u,v不在一條鏈上，假設(shè)v所在鏈長(zhǎng)度小于k，那么u~v的鏈長(zhǎng)顯然更長(zhǎng)，u,v應(yīng)在一條鏈上，矛盾
性質(zhì)3：任意節(jié)點(diǎn)到達(dá)根節(jié)點(diǎn)經(jīng)過(guò)的長(zhǎng)鏈數(shù)是n\sqrt{n}n?級(jí)的
由性質(zhì)2，每次跳躍到的新鏈長(zhǎng)度不會(huì)小于當(dāng)前鏈
最壞的情況，長(zhǎng)鏈長(zhǎng)度為1,2,3,…,n\sqrt{n}n?單調(diào)遞增
應(yīng)用
樹上k級(jí)祖先
洛谷P5903 【模板】樹上 k 級(jí)祖先
比較經(jīng)典的應(yīng)用
用樹上倍增解決的話可以O(shè)(nlogn)預(yù)處理，O(logn)回答
而長(zhǎng)鏈剖分可以O(shè)(nlogn)預(yù)處理，O(1)回答
先預(yù)處理出樹上倍增數(shù)組fa[u][i]，表示u的第2^i級(jí)祖先
并預(yù)處理出 1 ~ n 每個(gè)數(shù)二進(jìn)制下最高位的1的位置，即highbit(k)，以下記hkh_khk?
長(zhǎng)鏈剖分后，對(duì)于每條鏈，如果其長(zhǎng)度為 len
那么在頂點(diǎn)處記錄頂點(diǎn)向上的len個(gè)祖先和向下的len個(gè)鏈上的兒子
對(duì)于每次u，k的詢問(wèn)
先利用倍增數(shù)組將u跳到u的第2hk2^{h_k}2hk?級(jí)祖先，設(shè)剩下k′k'k′級(jí)，顯然k′<2hkk'<2^{h_k}k′<2hk?
而此時(shí)u所在長(zhǎng)鏈長(zhǎng)度>=2hk2^{h_k}2hk?>k’
所以再將u跳到鏈頂top[u]
之后剩下的級(jí)數(shù)直接在預(yù)處理出的向上向下的數(shù)組里O(1)查詢即可
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std
;
typedef long long lt
;
typedef unsigned int ui
;int read()
{int f
=1,x
=0;char ss
=getchar();while(ss
<'0'||ss
>'9'){if(ss
=='-')f
=-1;ss
=getchar();}while(ss
>='0'&&ss
<='9'){x
=x
*10+ss
-'0';ss
=getchar();}return f
*x
;
}const int maxn
=500010;
ui s
;
int n
,Q
,rt
;
struct node
{int v
,nxt
;}E
[maxn
<<1];
int head
[maxn
],tot
;
int hi
[maxn
];
int fa
[maxn
][25],dep
[maxn
],mxd
[maxn
];
int son
[maxn
],top
[maxn
];
vector
<int> pre
[maxn
],nxt
[maxn
];
lt ans
[maxn
*10];ui
get(ui x
)
{x
^=x
<<13;x
^=x
>>17;x
^=x
<<5;return s
=x
;
}void add(int u
,int v
)
{E
[++tot
].nxt
=head
[u
];E
[tot
].v
=v
;head
[u
]=tot
;
}void dfs1(int u
,int pa
)
{dep
[u
]=mxd
[u
]=dep
[pa
]+1;for(int i
=head
[u
];i
;i
=E
[i
].nxt
){int v
=E
[i
].v
;if(v
==pa
) continue;dfs1(v
,u
);if(mxd
[v
]>mxd
[u
]) mxd
[u
]=mxd
[v
],son
[u
]=v
; }
}void dfs2(int u
,int tp
)
{top
[u
]=tp
;if(u
==tp
){int x
=u
;for(int i
=0;i
<=mxd
[u
]-dep
[u
];++i
){pre
[u
].push_back(x
);x
=fa
[x
][0];}x
=u
;for(int i
=0;i
<=mxd
[u
]-dep
[u
];++i
){nxt
[u
].push_back(x
);x
=son
[x
];}}if(son
[u
]) dfs2(son
[u
],tp
);for(int i
=head
[u
];i
;i
=E
[i
].nxt
){int v
=E
[i
].v
;if(v
==son
[u
]||v
==fa
[u
][0]) continue;dfs2(v
,v
);}
}int solve(int u
,int k
)
{if(k
==0) return u
;u
=fa
[u
][hi
[k
]];k
-=1<<hi
[k
];k
-=dep
[u
]-dep
[top
[u
]];u
=top
[u
];return k
>=0?pre
[u
][k
]:nxt
[u
][-k
];
}int main()
{n
=read(); Q
=read(); s
=read();hi
[0]=-1;for(int i
=1;i
<=n
;++i
){fa
[i
][0]=read();add(fa
[i
][0],i
); add(i
,fa
[i
][0]);if(fa
[i
][0]==0) rt
=i
;hi
[i
]=hi
[i
>>1]+1;}dfs1(rt
,0); dfs2(rt
,rt
);for(int i
=1;(1<<i
)<=n
;++i
)for(int u
=1;u
<=n
;++u
)fa
[u
][i
]=fa
[fa
[u
][i
-1]][i
-1];for(int i
=1;i
<=Q
;++i
){int x
=(get(s
)^ans
[i
-1])%n
+1;int k
=(get(s
)^ans
[i
-1])%dep
[x
];ans
[i
]=solve(x
,k
);}lt res
=ans
[1];for(int i
=2;i
<=Q
;++i
)res
^=(lt
)i
*ans
[i
];printf("%lld",res
);return 0;
}
與深度有關(guān)的DP
CodeForces - 1009F Dominant Indices
題目大意: 給定一棵以1為根，n個(gè)節(jié)點(diǎn)的樹。設(shè) d(u,x)為u子樹中到u距離為x的節(jié)點(diǎn)數(shù)。
對(duì)于每個(gè)點(diǎn)，求使得d(u,x)最大的x，若有多個(gè)則輸出最小的x
題目分析：
設(shè)dp[u][k]表示u子樹中與u距離為k的節(jié)點(diǎn)數(shù)，
則 dp[u][k]=Σdp[v][k-1] (v為u的兒子)
設(shè)mxlen[u]表示u到最遠(yuǎn)的葉子結(jié)點(diǎn)的距離
每次轉(zhuǎn)移時(shí)，可以先選擇任意一個(gè)兒子v，把dp[v][]直接錯(cuò)位復(fù)制給dp[u][]
可通過(guò)數(shù)組的指針操作( dp[u]=dp[v]+1 )以O(shè)(1)實(shí)現(xiàn)
之后其他兒子的信息暴力合并到dp[u]
即對(duì)每個(gè)兒子v，按照上述轉(zhuǎn)移方程進(jìn)行mxlen[v]次更新
可以發(fā)現(xiàn)這樣做的復(fù)雜度直接由每次暴力合并的mxlen決定
如果我們把第一次直接復(fù)制的兒子選為長(zhǎng)鏈剖分的重兒子
那么暴力更新的mxlen就取得最小值，總復(fù)雜度就變成了O(n)
還有一點(diǎn)要注意的是dp數(shù)組顯然不能開dp[1e6][1e6]那么大
但由于所有長(zhǎng)鏈長(zhǎng)度和就是n，所以可以用指針指向一個(gè)大小為n的數(shù)組動(dòng)態(tài)使用空間
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std
;int read()
{int f
=1,x
=0;char ss
=getchar();while(ss
<'0'||ss
>'9'){if(ss
=='-')f
=-1;ss
=getchar();}while(ss
>='0'&&ss
<='9'){x
=x
*10+ss
-'0';ss
=getchar();}return f
*x
;
}const int maxn
=1000010;
int n
;
struct node
{int v
,nxt
;}E
[maxn
<<1];
int head
[maxn
],tot
;
int son
[maxn
],mxlen
[maxn
];
int buf
[maxn
];
int *dp
[maxn
],*cur
=buf
;
int ans
[maxn
];void add(int u
,int v
)
{E
[++tot
].nxt
=head
[u
];E
[tot
].v
=v
;head
[u
]=tot
;
}void dfs1(int u
,int pa
)
{for(int i
=head
[u
];i
;i
=E
[i
].nxt
){int v
=E
[i
].v
;if(v
==pa
) continue;dfs1(v
,u
);if(mxlen
[v
]>mxlen
[son
[u
]]) son
[u
]=v
;}mxlen
[u
]=mxlen
[son
[u
]]+1;
}void dfs2(int u
,int pa
)
{dp
[u
][0]=1;if(son
[u
]){dp
[son
[u
]]=dp
[u
]+1;dfs2(son
[u
],u
);ans
[u
]=ans
[son
[u
]]+1;}for(int i
=head
[u
];i
;i
=E
[i
].nxt
){int v
=E
[i
].v
;if(v
==son
[u
]||v
==pa
) continue;dp
[v
]=cur
; cur
+=mxlen
[v
];dfs2(v
,u
);for(int j
=1;j
<=mxlen
[v
];++j
){dp
[u
][j
]+=dp
[v
][j
-1];if(dp
[u
][j
]>dp
[u
][ans
[u
]]) ans
[u
]=j
;else if(dp
[u
][j
]==dp
[u
][ans
[u
]] && j
<ans
[u
]) ans
[u
]=j
;}}if(dp
[u
][ans
[u
]]==1) ans
[u
]=0;
}int main()
{n
=read();for(int i
=1;i
<n
;++i
){int u
=read(),v
=read();add(u
,v
); add(v
,u
);}dfs1(1,0); dp
[1]=cur
; cur
+=mxlen
[1];dfs2(1,0);for(int i
=1;i
<=n
;++i
)printf("%d\n",ans
[i
]);return 0;
}
總結(jié)
以上是生活随笔為你收集整理的长链剖分的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
