树上问题
树链剖分学习笔记
重链剖分
对树进行重链优先搜索，暴力求一条路径的复杂度为logn
模板
void tree_build(int u,int fa) {//重链优先搜索
siz[u]=1;
f[u]=fa;
hson[u]=0;
for(auto &v:adj[u]) {
deep[v]=deep[u]+1;
if(v==fa) continue;
tree_build(v,u);
siz[u]+=siz[v];
if(hson[u]==0||siz[v]>siz[hson[u]]) hson[u]=v;
}
}
void tree_decom(int u,int t) {//dfn序
top[u]=t;
cnt++;
dfn[u]=cnt;
rak[cnt]=u;
if(hson[u]!=0) {
tree_decom(hson[u],t);
for(auto &v:adj[u]) {
if(hson[u]!=v&&v!=f[u]) tree_decom(v,v);
}
}
rdfn[u]=cnt;
}
模板题1 洛谷模板
代码
while(m--) {
int op;
cin>>op;
if(op==1) {
int u,v,w;
cin>>u>>v>>w;
while(top[v]!=top[u]) {
if(deep[top[u]]>deep[top[v]]) {
modify(1,1,n,dfn[top[u]],dfn[u],w);
u=f[top[u]];
} else {
modify(1,1,n,dfn[top[v]],dfn[v],w);
v=f[top[v]];
}
}
if(dfn[v]<dfn[u]) swap(u,v);
modify(1,1,n,dfn[u],dfn[v],w);
} else if(op==2) {
int u,v;
cin>>u>>v;
int ans=0;
while(top[v]!=top[u]) {
if(deep[top[u]]>deep[top[v]]) {
ans+=query(1,1,n,dfn[top[u]],dfn[u]).sum;
u=f[top[u]];
} else {
ans+=query(1,1,n,dfn[top[v]],dfn[v]).sum;
v=f[top[v]];
}
}
if(dfn[v]<dfn[u]) swap(u,v);
ans+=query(1,1,n,dfn[u],dfn[v]).sum;
cout<<ans%p<<"\n";
} else if(op==3) {
int u,w;
cin>>u>>w;
modify(1,1,n,dfn[u],rdfn[u],w);
} else if(op==4) {
int u;
cin>>u;
int ans=query(1,1,n,dfn[u],rdfn[u]).sum;
cout<<ans%p<<"\n";
}
}
模板题2 Omsk Metro (hard version)
思路
代码
//线段树
Info operator + (const Info &a,const Info &b){
Info c;
c.sum=a.sum+b.sum;
c.lmin=min(a.lmin,a.sum+b.lmin);
c.lmax=max(a.lmax,a.sum+b.lmax);
c.rmin=min(b.rmin,b.sum+a.rmin);
c.rmax=max(b.rmax,b.sum+a.rmax);
c.min=min({a.min,a.rmin+b.lmin,b.min});
c.max=max({a.max,a.rmax+b.lmax,b.max});
return c ;
}
//main函数
for(auto it:que){
int u=it.first.first;
int v=it.first.second;
int value=it.second;
Info answer;//ans是最后的信息合并
if(deep[u]<deep[v]) swap(u,v);
Info left,right;
while(top[u]!=top[v]){//跳重链
if(deep[top[u]]>deep[top[v]]){
left=query(1,min(dfn[top[u]],dfn[u]),max(dfn[top[u]],dfn[u]))+left;
u=f[top[u]];
}
else{
right=query(1,min(dfn[top[v]],dfn[v]),max(dfn[top[v]],dfn[v]))+right;
v=f[top[v]];
}
}
if(dfn[u]<=dfn[v])
right=query(1,min(dfn[u],dfn[v]),max(dfn[u],dfn[v]))+right;
else
left=query(1,min(dfn[u],dfn[v]),max(dfn[u],dfn[v]))+left;
answer = rev(left)+right;
if(value>=answer.min&&value<=answer.max) cout<<"YES\n";
else cout<<"NO\n";
}
长链剖分
树上启发式合并学习笔记
模板
优化合并复杂度的方法
重链剖分
复杂度为logn
void tree_build(int u,int fa){
siz[u]=1;
hson[u]=0;
for(auto &v:adj[u]){
if(v==fa) continue;
dep[v]=dep[u]+1;
tree_build(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[hson[u]])hson[u]=v;
}
}
长链剖分
复杂度为根号n 用于优化树上dp
void tree_build(int u,int fa){
int maxdep=0;
deep[u]=1;
for(auto &v:adj[u]){
if(v==fa) continue;
f[v]=u;
tree_build(v,u);
if(deep[v]>maxdep){
maxdep=deep[v];
lson[u]=v;
}
deep[u]=max(deep[u],deep[v]+1);
}
}
合并信息模板
void calc(int u,int fa,int val) { //统计答案
if(val==1){//表示在增加这个节点时需要增加的操作
}
else{//表示在去掉这个节点时需要消去的操作
}
for(auto &v:adj[u]) {
if(v==fa||v==HH) continue;
calc(v,u,val);
}
}
void dsu(int u,int fa,int op){
for(auto &v:adj[u]){
if(v==fa||v==hson[u]) continue;
dsu(v,u,0);
}
if(hson[u]){
dsu(hson[u],u,1),
HH=hson[u];
}
calc(u,fa,1);
/*在这里对答案进行统计 一般每个dsu（u）的答案就是该节点的答案
*/
HH=0;
if(!op){calc(u,fa,-1);
}
}
题目选
模板题1 Lomsat gelral
寻找子树最大颜色的和
void calc(int u,int fa,int val) { //统计答案
if(val==1){
cntc[c[u]]++;//增加颜色操作
if(cntc[c[u]]>ma){
ma=cntc[c[u]];
res=c[u];
}
else if(cntc[c[u]]==ma)
res+=c[u];
}
}
else{
cntc[c[u]]--;//减少颜色
if(cntc[c[u]]>ma){
ma=cntc[c[u]];
res=c[u];
}
else if(cntc[c[u]]==ma){
res+=c[u];
}
}
//增加或者减少后，统计新的值
for(auto &v:adj[u]) {
if(v==fa||v==HH) continue;
calc(v,u,val);
}
}
void dsu(int u,int fa,int op) { //op=1 传递 否则保留
for(auto &v:adj[u]) {
if(v==fa||v==hson[u]) continue;
dsu(v,u,0);//先遍历轻儿子
}
if(hson[u]) dsu(hson[u],u,1),HH=hson[u];
calc(u,fa,1);
ans[u]=res; //统计每个点答案
HH=0;
if(!op) calc(u,fa,-1),res=ma=0;//表示不用传递，要把res清空
}
模板题2 Blood Cousins Return
寻找子树每一层不同颜色的个数
用set去统计对于每个dsu到的点的节点信息 set表示离根节点距离的名字
void calc(int u,int fa,int val) { //统计答案
if(val==1){
v[dep[u]].insert(s[u]);//加入节点
}
else{
v[dep[u]].erase(s[u]);
}
for(auto &v:adj[u]) {
if(v==fa||v==HH) continue;
calc(v,u,val);
}
}
void dsu(int u,int fa,int op){
for(auto &v:adj[u]){
if(v==fa||v==hson[u]) continue;
dsu(v,u,0);
}
if(hson[u]){
dsu(hson[u],u,1),
HH=hson[u];
}
calc(u,fa,1);
for(auto &it:Q[u]){
int h=it[0],id=it[1];
ans[id]=v[dep[u]+h].size();
}
HH=0;
if(!op){calc(u,fa,-1);
}
}
模板题3 彩色的树
处理子树内某个深度差内的节点信息
考虑把信息全塞set里面 在从下往上dsu的时候，传递的同时删除深度越出的节点
void del(int x){//删除过多节点
if(x>n) return;
while(!deps[x].empty()){
auto it=deps[x].begin();
if(cntc[*it]==1) res--;
cntc[*it]--;
deps[x].erase(it);
}
}
void calc(int u,int fa,int val,int lim,int Son) { //统计答案
if(deep[u]>lim) return;
if(val==1){
if(cntc[c[u]]==0){
res++;
} deps[deep[u]].insert(c[u]);
}
else {
if(cntc[c[u]]==1){
res--;
}
auto it=deps[deep[u]].find(c[u]);
deps[deep[u]].erase(it);
}
cntc[c[u]]+=val;
for(auto &v:adj[u]) {
if(v==fa||(val==1&&v==Son)) continue;
calc(v,u,val,lim,Son);
}
}
void dsu(int u,int fa,int op) { //op=1 传递 否则保留
for(auto &v:adj[u]) {
if(v==fa||v==hson[v]) continue;
dsu(v,u,0);//先遍历轻儿子
}
if(hson[u]!=-1) dsu(hson[u],u,1);
calc(u,fa,1,deep[u]+k,hson[u]);
ans[u]=res;
if(!op) calc(u,fa,-1,deep[u]+k,hson[u]);//表示不用传递
else{ del(deep[u]+k);
}
}
点分治
模板
void dfs(int x, int fa, ll sum, ll mx){
ll s = sum + a[x];
ll mm = max(mx, a[x]);
o.push_back({mm, s});
all1.push_back({mm, s});
vx.push_back(s);
for(auto v : adj[x]){
if(v == fa || del[v]) continue;
dfs(v, x, s, mm);
}
}
void calc(int x){
//统计答案
}
void getroot(int x, int fa){
sz[x] = 1;
int max_part = 0;
for(auto &v : adj[x]){
if(v == fa || del[v]) continue;
getroot(v, x);
sz[x] += sz[v];
max_part = max(max_part, sz[v]);
}
max_part = max(max_part, sum - sz[x]);
if(max_part < tmp){
tmp = max_part;
root = x;
}
}
void divide(int x){
calc(x);
del[x] = 1;
for(auto &v : adj[x]){
if(del[v]) continue;
tmp = sum = sz[v];
getroot(v, 0);
divide(root);
}
}
题目选
模板题1 聪聪可可
代码
#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
int tmp,sum,root,ans=0,del[MAXN],sz[MAXN];
int f[3];
vector<pair<int,int> > adj[MAXN];
void dfs(int u, int fa, ll D) {
for(auto it : adj[u]) {
int v=it.first;
int w=it.second;
if(v == fa || del[v]) continue;
f[(D+w)%3]++;
dfs(v, u, w+D);
}
}
int calc(int u,int D) {
//统计答案
memset(f,0,sizeof(f));
f[D%3]++;
dfs(u,0,D);
return f[0]*f[0]+f[1]*f[2]*2;
}
void getroot(int x, int fa) {
sz[x] = 1;
int max_part = 0;
for(auto &it : adj[x]) {
int v=it.first;
int w=it.second;
if(v == fa || del[v]) continue;
getroot(v, x);
sz[x] += sz[v];
max_part = max(max_part, sz[v]);
}
max_part = max(max_part, sum - sz[x]);
if(max_part < tmp) {
tmp = max_part;
root = x;
}
}
void divide(int x) {
ans+=calc(x,0);
del[x] = 1;
for(auto &it : adj[x]) {
int v=it.first;
int w=it.second;
if(del[v]) continue;
ans-=calc(v,w);
tmp = sum = sz[v];
getroot(v, 0);
divide(root);
}
}
void solve() {
int n;
cin>>n;
for(int i=1; i<n; i++) {
int u,v,w;
cin>>u>>v>>w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
tmp=sum=n;
getroot(1,0);
getroot(root,0);
divide(root);
// ans+=n;
int fm=n*n;
int k=__gcd(ans,fm);
cout<<ans/k<<"/"<<fm/k;
}
signed main() {
solve();
}
线段树补充
线段树维护矩阵和
矩阵快速幂
和普通快速幂同理
int M;
struct matrix
{
ll x[M+1][M+1];
matrix(){memset(x,0,sizeof(x));}
};
matrix mpow(matrix &a,ll m)//矩阵a的m次方
{
matrix res;
for(int i=1;i<=M;i++) res.x[i][i]=1;//单位矩阵
while(m>0)
{
if(m&1) res=multiply(res,a);
a=multiply(a,a);
m>>=1;
}
return res;
}
matrix multiply(matrix &a,matrix &b)
{
matrix c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c.x[i][j]+=a.x[i][k]*b.x[k][j];
return c;
}
对某个数的重复操作可以用矩阵乘法来维护
比如说 要把A，B中的A变成A+B， 就可以对
$$
\left[
\begin{matrix}
A & B\
\end{matrix}
\right]
$$
右乘一个
$$
\left[
\begin{matrix}
1 & 1 \
0 & 1
\end{matrix}
\right]
$$
矩阵乘法是要有顺序的，在重复的情况下可以用快速幂加速
否则用线段树维护区间的加
模板题1 Addition Robot
对于这道题，要有顺序的处理A和B矩阵的乘法顺序
因此可以用线段树维护乘法，一直向右乘就行了
在放懒标记的时候，交换矩阵的对角（
#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 1e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
struct matrix {
ll x[3][3];
matrix() {
memset(x,0,sizeof(x));
}
};
matrix multiply(matrix &a,matrix &b) {
matrix c;
for(int i=1; i<=2; i++)
for(int j=1; j<=2; j++)
for(int k=1; k<=2; k++)
c.x[i][j]+=a.x[i][k]*b.x[k][j]%mod;
return c;
}
matrix mpow(matrix &a,ll m) { //矩阵a的m次方
matrix res;
for(int i=1; i<=2; i++) res.x[i][i]=1; //单位矩阵
while(m>0) {
if(m&1) res=multiply(res,a);
a=multiply(a,a);
m>>=1;
}
return res;
}
struct Info {
matrix x;
};
Info operator +(const Info &a,const Info &b) {
Info c;
matrix tmpa,tmpb;
tmpa=a.x;
tmpb=b.x;
c.x=multiply(tmpa,tmpb);
return c;
}
struct node {
int lazy;
Info val;
} seg[MAXN<<2];
void up(int id) {
seg[id].val=seg[id<<1].val+seg[id<<1|1].val;
}
void settag(int id,int l,int r,int tag) {
seg[id].lazy^=1;
swap(seg[id].val.x.x[1][2],seg[id].val.x.x[2][1]);
swap(seg[id].val.x.x[2][2],seg[id].val.x.x[1][1]);
}
void down(int id,int l,int r) {
if(seg[id].lazy==0) return;
int mid=l+r>>1;
settag(id<<1,l,mid,seg[id].lazy);
settag(id<<1|1,mid+1,r,seg[id].lazy);
seg[id].lazy=0;
}
char a[MAXN];
matrix A,B;
void build(int id,int l,int r) {
if(l==r) {
if(a[l]=='A')
seg[id].val.x=A;
else seg[id].val.x=B;
seg[id].lazy=0;
return;
}
int mid=l+r>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
up(id);
}
void modify(int id,int l,int r,int ql,int qr,int val) {
if (ql<=l&&r<=qr) {
settag(id,l,r,val);
return;
}
down(id,l,r);
int mid =(l+r) >> 1;
if (qr<=mid)
modify(id <<1,l,mid,ql,qr,val);
else if (ql>mid)
modify(id<<1|1, mid+1,r,ql,qr,val);
else {
modify(id<<1,l,mid,ql,qr,val);
modify(id<<1|1,mid+1,r,ql,qr,val);
}
up(id);
}
Info query(int id,int l ,int r,int ql,int qr) {
if(ql<=l&&r<=qr) {
return seg[id].val;
}
down(id,l,r);
int mid=l+r>>1;
if(qr<=mid) return query(id<<1,l,mid,ql,qr);
else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
else return query(id<<1,l,mid,ql,qr)+query(id<<1|1,mid+1,r,ql,qr);
}
void solve() {
A.x[1][1]=1;
A.x[1][2]=0;
A.x[2][1]=1;
A.x[2][2]=1;
B.x[1][1]=1;
B.x[1][2]=1;
B.x[2][1]=0;
B.x[2][2]=1;
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i];
build(1,1,n);
while(m--) {
int op;
cin>>op;
if(op==2) {
int l,r;
cin>>l>>r;
int aa,bb;
cin>>aa>>bb;
matrix tmp;
tmp.x[1][1]=aa;
tmp.x[1][2]=bb;
matrix k;
k=query(1,1,n,l,r).x;
tmp=multiply(tmp,k);
cout<<tmp.x[1][1]%mod<<" "<<tmp.x[1][2]%mod<<'\n';
} else {
int l,r;
cin>>l>>r;
modify(1,1,n,l,r,1);
}
}
}
signed main() {
solve();
}