posted on 2022-07-20 18:59:16 | under 模板 | source
0x00 模板(P3806)
给定 \(n,k\) 和一棵树,计算
\[\sum\limits_{i,j\leq n}[{\tt dist}(i,j)=k] \]即树上距离为 \(k\) 的点对数量。
点分治,令 \({\tt solve}(x)\) 表示我们要计算 \(u\) 所在连通块的答案。选一个根 \(u\)(它应该是重心),把点对分成两类:
- 路径经过 \(u\) 的:在 \({\tt calc}(u)\) 中计算,表示计算经过 \(u\) 的点对数量。
- 路径不经过 \(u\) 的:那么这两个点在 \(u\) 的某个儿子的子树里,删掉 \(u\),继续递归 \({\tt solve}(v)\) 计算。
将这个过程递归下去,就一定能解决所有点对,因为每个根都会被枚举。
选定的根 \(u\) 应该是这棵树的重心,考虑重心的定义:删掉一个点后剩余的最大连通块最小(指点数),那么这点称作树的重心。重心最多有两个,最少有一个。
node getroot(int u,int fa,int T){
node res=node(1e9,0);
siz[u]=1,smx[u]=0;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(v==fa||cut[v]) continue;
res=min(res,getroot(v,u,T));
siz[u]+=siz[v];
smx[u]=max(smx[u],siz[v]);
}
smx[u]=max(smx[u],T-siz[u]);
return min(res,node(smx[u],u));
}
注意这个 \(\min\),这有一组数据供自测。
把递归的每一层的重心连起来连成一棵树,这棵树叫作点分树。从点分树上的一个点往上跳,点分树的子树大小翻倍,所以点分树只有 \(O(\log n)\) 层,总时间复杂度为 \(T(n)=2T(\frac{n}{2})+O({\tt calc})\)。
//写法一
LL solve(int u,int k){
cut[u]=1;
LL res=calc(u,k);
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(cut[v]) continue;
res+=solve(getroot(v,0,siz[v]).second,k);
}
return res;
}
//写法二:容斥
LL solve(int u){
cut[u]=1;
LL res=calc(u,0);
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(cut[v]) continue;
res-=calc(v,g[i].w);
res+=solve(getroot(v,0,siz[v]).second);
}
return res;
}
solve(getroot(1,0,n).second,k);
你注意到这个递归调用很奇怪,怎么能说 \(siz_v\) 是连通块大小呢?膜拜了 这位大佬 后,你不觉得奇怪了,它真的是对的。
那么 \({\tt calc}(u)\) 应该怎么写?
- \({\tt getdist}(u)\):从根出发,把每个点到根的距离存到一个数组里。
- 两种写法:
- 写法一:\({\tt getdist}(u)\) 的同时记录这些点来自哪棵子树,计算答案时严格按照这个限制做(即不能有两个点在同一子树中),可以双指针。
- 写法二:我不管什么子树不子树的,我容斥,全部点对减去在子树内的点对就是 \(u\) 的答案。注意写法,容斥的时候传下去的初始值要一样。
bool cmp(int x,int y){return dis[x]<dis[y];}
void getdist(int u,int fa,int w,int from){
dis[id[++tot]=u]=w,fom[u]=from;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(v==fa||cut[v]) continue;
getdist(v,u,w+g[i].w,from);
}
}
//写法一
LL calc(int u,int){
dis[id[tot=1]=u]=0,fom[u]=u;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(cut[v]) continue;
getdist(v,u,g[i].w,v);
}
sort(id+1,id+tot+1,cmp);
for(int i=1;i<=m;i++){
int k=q[i];LL res=0;
if(k<0) continue;
for(int L=1,R=tot;L<R;){
if(dis[id[L]]+dis[id[R]]<k) L++;
else if(dis[id[L]]+dis[id[R]]>k) R--;
else res+=fom[id[L]]!=fom[id[R]],L++;
if(res) break;
}
if(res) q[i]=-q[i];
}
return 19491001;
}
//写法二:O(n^2) 暴力
于是我们解决了这一题,这是 P3806 的代码实现。
0x01(P4178)
给定 \(n,k\) 和一棵树,计算
\[\sum\limits_{i,j\leq n}[{\tt dist}(i,j)\leq k] \]没有什么区别,就是这个 \(\leq\),也可以双指针,注意写法:
template<int N> struct counter{
int c[N+10],u[N+10][2],tot;
counter():tot(0){memset(c,0,sizeof c);}
void insert(int k,int p){u[++tot][0]=k,u[tot][1]=p,c[p]+=k;}
int& operator[](int i){return c[i];}
void undo(int){c[u[tot][1]]-=u[tot][0],tot--;}
void rollback(){for(;tot>0;undo(1));}
};
LL calc(int u,int k){
dis[id[tot=1]=u]=0,fom[u]=u;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(cut[v]) continue;
getdist(v,u,g[i].w,v);
}
sort(id+1,id+tot+1,cmp);
for(int i=1;i<=tot;i++) c.insert(1,fom[id[i]]);
LL res=0;
for(int L=1,R=tot;L<=tot;L++){
while(dis[id[L]]+dis[id[R]]>k&&R>=1) c.undo(fom[id[R--]]);
if(dis[id[L]]+dis[id[R]]<=k) res+=R-c[fom[id[L]]];
//当前 [1,R] 可以和 L 配对,但要减掉和 L 同子树的点。
}
c.rollback();
return res;
}
0x02(P2634)
给定 \(n\) 和一棵树,计算
\[\sum\limits_{i,j\leq n}[3|{\tt dist}(i,j)] \]还是一样的,考虑算出 \(c_0,c_1,c_2\) 表示一共有多少条路径长度模 \(3\) 是 \(0,1,2\)。用容斥的写法(双指针没有单调性)。方案数为 \((c_0)^2+2c_1c_2\)。
关于这个方案数,有时 \((i,j)\) 和 \((j,i)\) 会算两次,有时 \((i,i)\) 会混进答案(这会有 \(n\) 个),看题决定写法。
标签:int,res,tt,tot,Centroid,siz,Decomposition,id,模板 From: https://www.cnblogs.com/caijianhong/p/16863434.html