树链剖分记牢模板+例题
这是对点权计算的板子
const int N = 1e5 + 5;
vector<int> g[N];
int fa[N], dp[N], sz[N], son[N], top[N], dfn[N], to[N], cnt = 0, n;
void dfs1(int u, int o) {
fa[u] = o;
sz[u] = 1;
dp[u] = dp[o] + 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != o) {
dfs1(v, u);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
}
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
to[cnt] = u;
if(!son[u]) return ;
dfs2(son[u], t);
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if(v != fa[u] && v != son[u]) dfs2(v, v);
}
}
void add(int u, int v, int x) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) update(dfn[fu], dfn[u], x, 1, 1, n), u = fa[fu], fu = top[u];
else update(dfn[fv], dfn[v], x, 1, 1, n), v = fa[fv], fv = top[v];
}
if(dfn[u] <= dfn[v]) update(dfn[u], dfn[v], x, 1, 1, n);
else update(dfn[v], dfn[u], x, 1, 1, n);
}
int solve(int u, int v) {
int ans = 0, fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) ans += query(dfn[fu], dfn[u], 1, 1, n), u = fa[fu], fu = top[u];
else ans += query(dfn[fv], dfn[v], 1, 1, n), v = fa[fv], fv = top[v];
}
if(dfn[u] <= dfn[v]) ans += query(dfn[u], dfn[v], 1, 1, n);
else ans += query(dfn[v], dfn[u], 1, 1, n);
return ans;
}
int lca(int u, int v) {
int fu = top[u], fv = top[v];
while(fu != fv) {
if(dp[fu] >= dp[fv]) u = fa[fu], fu = top[u];
else v = fa[fv], fv = top[v];
}
if(dp[u] <= dp[v]) return u;
else v;
}
下面是对于计算边权的板子的例题：（题目大意是：对于P ：u，v表示u到v之间的边+1。对于Q：u，v表示输出u到v之间边之和；）
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。千万注意俩者在add和solve函数部分的区别！！！！！！！！！！！！！！！
https://vjudge.net/problem/SPOJ-GRASSPLA
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int M=1e5+5;
vector<int>g[M];
int fa[M],son[M],sz[M],dfn[M],top[M],deep[M];
ll tree[M<<2],lazy[M<<2];
int cnt,n;
void dfs1(int u,int from){
fa[u]=from;
sz[u]=1;
deep[u]=deep[from]+1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v!=from){
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])
son[u]=v;
}
}
}
void dfs2(int u,int t){
top[u]=t;
dfn[u]=++cnt;
if(!son[u])
return;
dfs2(son[u],t);
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v!=fa[u]&&v!=son[u])
dfs2(v,v);
}
}
void pushdown(int root,int len){
int sign=lazy[root];
lazy[root<<1]+=sign;
lazy[root<<1|1]+=sign;
tree[root<<1]+=(len-(len>>1))*1ll*sign;
tree[root<<1|1]+=(len>>1)*1ll*sign;
lazy[root]=0;
}
void update(int L,int R,int x,int root,int l,int r){
if(L<=l&&r<=R){
tree[root]+=x*(r-l+1)*1ll;
lazy[root]+=x;
return ;
}
if(lazy[root])
pushdown(root,r-l+1);
int midd=(l+r)>>1;
if(L<=midd)
update(L,R,x,root<<1,l,midd);
if(R>midd)
update(L,R,x,root<<1|1,midd+1,r);
tree[root]=tree[root<<1]+tree[root<<1|1];
}
void add(int v,int u,int x){
int fv=top[v],fu=top[u];
while(fv!=fu){
if(deep[fu]>=deep[fv])
update(dfn[fu],dfn[u],x,1,1,n),u=fa[fu],fu=top[u];
else
update(dfn[fv],dfn[v],x,1,1,n),v=fa[fv],fv=top[v];
}
if(dfn[u] <= dfn[v])
update(dfn[u]+1,dfn[v],x,1,1,n);
else
update(dfn[v]+1,dfn[u],x,1,1,n);
}
ll query(int L,int R,int root,int l,int r){
if(L<=l&&r<=R)
return tree[root];
ll ans=0;
int midd=l+r>>1;
if(lazy[root])
pushdown(root,r-l+1);
if(L<=midd)
ans+=query(L,R,root<<1,l,midd);
if(R>midd)
ans+=query(L,R,root<<1|1,midd+1,r);
tree[root]=tree[root<<1]+tree[root<<1|1];
return ans;
}
ll solve(int v,int u){
ll ans=0;
int fu=top[u],fv=top[v];
while(fu!=fv){
if(deep[fu]>=deep[fv])
ans+=query(dfn[fu],dfn[u],1,1,n),u=fa[fu],fu=top[u];
else
ans+=query(dfn[fv],dfn[v],1,1,n),v=fa[fv],fv=top[v];
}
if(dfn[u] <= dfn[v]) ans += query(dfn[u]+1, dfn[v], 1, 1, n);
else ans += query(dfn[v]+1, dfn[u], 1, 1, n);
return ans;
}
int main(){
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(1,1);
dfs2(1,1);
/*for(int i=1;i<=n;i++)
cout<<dfn[i]<<"~";
cout<<endl;*/
while(m--){
char s[2];
int x,y;
scanf("%s%d%d",s,&x,&y);
if(s[0]=='P')
add(x,y,1);
else
printf("%lld\n",solve(x,y));//
}
return 0;
}
更多精彩
