树链剖分[学习笔记]

news/2024/9/20 5:31:39

树链剖分

壹.

树剖，就是树链剖分，将一棵树剖分成一堆链 (如说 \(\dots\) )

本文主要介绍重链剖分。

树剖成链之后一段重链上的 \(dfs\) 序是连续的，那么我们就可以对 \(dfs\) 序使用一些数据结构(树状数组、线段树等)

\(1\).一些变量及意义

  • \(fa[x]\) \(x\) 的父节点
  • \(depth[x]\) \(x\) 的深度
  • \(siz[x]\) \(x\) 的子树大小，我们将根据他求重儿子
  • \(wson[x]\) \(x\) 的重儿子，即 \(x\) 的儿子中子树最大的
  • \(top[x]\) \(x\) 所在重链的链顶
  • \(dfn[x]\) \(x\) 的 \(dfs\) 序，即第二次访问到 \(x\) 的时间
  • \(id[i]\) 用来求 \(dfs\) 序为 \(i\) 的节点，即 \(id[dfn[x]]=x\)
  • \(out[x]\) 第二次访问到 \(x\) 的时间

说白了，树剖就是用来求上述东西，然后就可以利用上述东西搞事情了。

\(2\).两遍 \(dfs\) 完成树剖

  • 第一遍，我们可以轻松求出 \(fa[x]\)，\(depth[x]\)，\(siz[x]\)，\(wson[x]\)。
void dfs(int x){depth[x]=depth[fa[x]]+1;siz[x]=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x])  continue;fa[y]=x;dfs(y);if(siz[y]>siz[wson[x]])  wson[x]=y;//更新重儿子siz[x]+=siz[y];}
}

偷的图

  • 第二遍，主要求 \(dfs\) 序，顺便求下 \(top\) 。我们优先跑重儿子，就可以保证重链上的 \(dfs\) 序连续。
void dfs(int x,int tp){top[x]=tp;dfn[x]=++t;id[t]=x;if(wson[x])  dfs(wson[x],tp);for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x]||y==wson[x])  continue;dfs(y,y);//显然，轻儿子一定是重链的链顶}out[x]=t;
}

\(3\).求 \(LCA\)

我们从 \(u,v\) 分别上跳，跳到链顶，为了防止它们 像小H和小C一样 错过，所以我们每次选择链顶深度大的上跳，到一条链上后，深度小的即为 \(LCA\)。

int LCA(int u,int v){while(top[u]!=top[v]){if(depth[top[u]]<depth[top[v]])  swap(u,v);u=fa[top[u]];}return (depth[u]<depth[v] ? u : v);
}

跳重链的复杂度为 \(O(\log _2n)\) 但是它严格跑不满，所以它的速度薄纱倍增和 \(tarjan\) 。

\(4\).一些性质和利用

  • 树剖成链之后一段重链上的 \(dfs\) 序是连续的，用线段树等即可优秀地维护重链信息
  • 从任意节点跳到根节点最多跳 \(\log _2n\) 次，多数情况下跑不满。

之前总听人说树剖码量大，学了之后才发现树剖就那么几行，不太会变，真正码量大的是维护重链信息的数据结构——比如线段树。如果你对线段树很怵头，先学好线段树吧，或者说，打完树剖你也就不怵头了。

贰.\(hs\)题单

\(T_A\) ZJOI2008 树的统计

板子，树剖，线段树维护单点修改，最大值和区间和，跳重链求解即可。

注意此题值域 \([-30000,30000]\) ，求最大值时注意初值赋极小

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
const int N=3*1e4+10;
#define INF 30010
int n;
int w[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}namespace Tree_Chain_Partition{int fa[N],depth[N],wson[N],siz[N];int top[N],dfn[N],id[N],out[N],t;void dfs1(int x){depth[x]=depth[fa[x]]+1;siz[x]=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x])  continue;fa[y]=x;dfs1(y);if(siz[y]>siz[wson[x]])  wson[x]=y;siz[x]+=siz[y];}}void dfs2(int x,int tp){top[x]=tp;dfn[x]=++t;id[t]=x;if(wson[x])  dfs2(wson[x],tp);for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x]||y==wson[x])  continue;dfs2(y,y);}out[x]=t;}int LCA(int u,int v){while(top[u]!=top[v]){if(depth[top[u]]<depth[top[v]])  swap(u,v);u=fa[top[u]];}return (depth[u]<depth[v]?u:v);}
} using namespace Tree_Chain_Partition;namespace Segment_Tree{struct Tree{int sum,mx,l,r;#define l(i) tr[i].l#define r(i) tr[i].r#define sum(i) tr[i].sum#define mx(i) tr[i].mx#define ls(i) (i<<1)#define rs(i) (i<<1|1)}tr[N<<2];void pushup(int i){sum(i)=sum(ls(i))+sum(rs(i));mx(i)=max(mx(ls(i)),mx(rs(i)));}void build(int i,int l,int r){l(i)=l;r(i)=r;if(l==r){mx(i)=sum(i)=w[id[l]];return;}int mid=(l+r)>>1;build(ls(i),l,mid);build(rs(i),mid+1,r);pushup(i);return;}void modify(int i,int x,int k){if(l(i)==r(i)){sum(i)=mx(i)=k;return;}int mid=(l(i)+r(i))>>1;if(x<=mid)  modify(ls(i),x,k);else  modify(rs(i),x,k);pushup(i);return;}int asksum(int i,int ql,int qr){int l=l(i),r=r(i);if(ql<=l&&r<=qr)  return sum(i);int mid=(l+r)>>1,res=0;;if(ql<=mid)  res+=asksum(ls(i),ql,qr);if(mid<qr)  res+=asksum(rs(i),ql,qr);return res;  }int askmax(int i,int ql,int qr){int l=l(i),r=r(i);if(ql<=l&&r<=qr)  return mx(i);int mid=(l+r)>>1,res=-INF;if(ql<=mid)  res=max(res,askmax(ls(i),ql,qr));if(mid<qr)  res=max(res,askmax(rs(i),ql,qr));return res;}
}using namespace Segment_Tree;
int ans;int qsum(int u,int lca){int res=0;while(depth[top[u]]>depth[lca]&&top[u]!=top[lca]){res+=asksum(1,dfn[top[u]],dfn[u]);u=fa[top[u]];}res+=(u==lca?w[u]:asksum(1,dfn[lca],dfn[u]));return res;
}int qmax(int u,int lca){int res=-INF;while(depth[top[u]]>depth[lca]&&top[u]!=top[lca]){res=max(res,askmax(1,dfn[top[u]],dfn[u]));u=fa[top[u]];}res=max(res,(u==lca?w[u]:askmax(1,dfn[lca],dfn[u])));return res;
}signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read;for(int i=1,a,b;i<n;i++)  a=read,b=read,add(a,b),add(b,a);for(int i=1;i<=n;i++)  w[i]=read;dfs1(1);dfs2(1,1);build(1,1,t);int T;T=read;char op[7];int u,v,k;while(T-->0){scanf("%s",op);u=read;if(op[0]=='C'){k=read;w[u]=k;modify(1,dfn[u],k);}else{v=read;int lca=LCA(u,v);if(op[1]=='S'){ans=-w[lca];ans+=qsum(u,lca);ans+=qsum(v,lca);}else{ans=-INF;ans=max(ans,qmax(u,lca));ans=max(ans,qmax(v,lca));}write(ans),pt;}}return 0;
}

\(T_B\) HAOI2015 树上操作

板子，树剖，线段树维护区间修改区间求和。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 100010
int n,w[N];
int m;namespace Tree_Chain_Partition{struct EDGE{int next,to;}e[N<<1];int head[N],total;void add(int u,int v){e[++total]={head[u],v};head[u]=total;}int fa[N],wson[N],depth[N],siz[N];int top[N],dfn[N],out[N],id[N],t;void dfs1(int x){depth[x]=depth[fa[x]]+1;siz[x]=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x])  continue;fa[y]=x;dfs1(y);if(siz[y]>siz[wson[x]])  wson[x]=y;siz[x]+=siz[y];}}void dfs2(int x,int tp){top[x]=tp;dfn[x]=++t;id[t]=x;if(wson[x])  dfs2(wson[x],tp);for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x]||y==wson[x])  continue;dfs2(y,y);}out[x]=t;}
} using namespace Tree_Chain_Partition;namespace Segment_Tree{struct Tree{int l,r,sum,lazy;#define l(i) tr[i].l#define r(i) tr[i].r#define sum(i) tr[i].sum#define lazy(i) tr[i].lazy#define ls(i) (i<<1)#define rs(i) (i<<1|1)}tr[N<<2];void pushup(int i){sum(i)=sum(ls(i))+sum(rs(i));}void pushdown(int i){if(!lazy(i))  return;sum(ls(i))+=(r(ls(i))-l(ls(i))+1)*lazy(i);sum(rs(i))+=(r(rs(i))-l(rs(i))+1)*lazy(i);lazy(ls(i))+=lazy(i);lazy(rs(i))+=lazy(i);lazy(i)=0;return;}void build(int i,int l,int r){l(i)=l,r(i)=r;if(l==r){sum(i)=w[id[l]];return;}int mid=(l+r)>>1;build(ls(i),l,mid);build(rs(i),mid+1,r);pushup(i);return;}void modify(int i,int x,int k){int l=l(i),r=r(i);if(l==r){sum(i)+=k;return;}pushdown(i);int mid=(l+r)>>1;if(x<=mid)  modify(ls(i),x,k);else  modify(rs(i),x,k);pushup(i);return;}void update(int i,int ml,int mr,int k){int l=l(i),r=r(i);if(ml<=l&&r<=mr){lazy(i)+=k;sum(i)+=(r(i)-l(i)+1)*k;return;}pushdown(i);int mid=(l+r)>>1;if(ml<=mid)  update(ls(i),ml,mr,k);if(mid<mr)  update(rs(i),ml,mr,k);pushup(i);return;}int query(int i,int ql,int qr){int l=l(i),r=r(i);if(ql<=l&&r<=qr)  return sum(i);pushdown(i);int mid=(l+r)>>1,res=0;if(ql<=mid)  res+=query(ls(i),ql,qr);if(mid<qr)  res+=query(rs(i),ql,qr);pushup(i);return res;}} using namespace Segment_Tree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read;m=read;for(int i=1;i<=n;i++)  w[i]=read;for(int i=1,a,b;i<n;i++)  a=read,b=read,add(a,b),add(b,a);dfs1(1);dfs2(1,1);build(1,1,t);int op,u,v,k,ans;while(m-->0){op=read;u=read;switch(op){case 1:k=read;modify(1,dfn[u],k);break;case 2:k=read;update(1,dfn[u],out[u],k);break;case 3:ans=0;while(u){ans+=query(1,dfn[top[u]],dfn[u]);u=fa[top[u]];}write(ans);pt;break;default:break;}}return 0;
}

\(T_C\) 难存的情缘

vjudge上没找着，挂学校OJ吧

板子，树剖，将边权下放到点上，然后单点修改区间查询最大值即可。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 10010
int n,w[N];namespace Tree_Chain_Partition{struct EDGE{int next,to,ww,number;}e[N<<1];int head[N],total;int dot[N];void add(int u,int v,int ww,int id){e[++total]={head[u],v,ww,id};head[u]=total;}int fa[N],depth[N],wson[N],siz[N];int top[N],dfn[N],id[N],t;void dfs1(int x){depth[x]=depth[fa[x]]+1;siz[x]=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x])  continue;fa[y]=x;// cerr<<x<<"->"<<y<<'\n';// cerr<<"e["<<i<<"].num="<<e[i].number<<'\n';// cerr<<"e["<<i<<"].ww="<<e[i].ww<<'\n';dot[e[i].number]=y;w[y]=e[i].ww;dfs1(y);if(siz[y]>siz[wson[x]])  wson[x]=y;siz[x]+=siz[y];}}void dfs2(int x,int tp){top[x]=tp;dfn[x]=++t;id[t]=x;if(wson[x])  dfs2(wson[x],tp);for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x]||y==wson[x])  continue;dfs2(y,y);}}
} using namespace Tree_Chain_Partition;namespace Segment_Tree{struct Tree{int l,r,mx;#define ls(i) (i<<1)#define rs(i) (i<<1|1)#define l(i) tr[i].l#define r(i) tr[i].r#define mx(i) tr[i].mx}tr[N<<2];void pushup(int i){mx(i)=max(mx(ls(i)),mx(rs(i)));}void build(int i,int l,int r){l(i)=l,r(i)=r;if(l==r){mx(i)=w[id[l]];return;}int mid=(l+r)>>1;build(ls(i),l,mid);build(rs(i),mid+1,r);pushup(i);return;}void modify(int i,int x,int k){int l=l(i),r=r(i);if(l==r){mx(i)=k;return;}int mid=(l+r)>>1;if(x<=mid)  modify(ls(i),x,k);else  modify(rs(i),x,k);pushup(i);return;}int query(int i,int ql,int qr){int l=l(i),r=r(i);if(ql<=l&&r<=qr){return mx(i);}int mid=(l+r)>>1,res=0;if(ql<=mid)  res=max(res,query(ls(i),ql,qr));if(mid<qr)  res=max(res,query(rs(i),ql,qr));return res;}
} using namespace Segment_Tree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read;for(int a,b,c,i=1;i<n;i++){a=read,b=read,c=read;add(a,b,c,i);add(b,a,c,i);}dfs1(1);dfs2(1,1);build(1,1,t);char op[7];int u,v,k,i,ans;while(1){scanf("%s",op);switch(op[0]){case 'C':i=read,k=read;u=dot[i];modify(1,dfn[u],k);break;case 'Q':u=read,v=read;ans=0;while(top[u]!=top[v]){if(depth[top[u]]<depth[top[v]])  swap(u,v);ans=max(ans,query(1,dfn[top[u]],dfn[u]));u=fa[top[u]];}ans=max(ans,(depth[u]<depth[v]?query(1,dfn[wson[u]],dfn[v]):query(1,dfn[wson[v]],dfn[u])));write(ans);pt;break;default:return 0;}}return 0;
}

\(T_D\) 货车运输

打 \(LCA\) 时打过一次，一样的思路，把倍增换成树剖。

首先一个 \(kruskal\) 重构树，然后就很板了，树剖，线段树维护区间最小值。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 20010
#define M 50010
int n,m;
int w[N<<1];
namespace klskr{struct EDGE{int next,from,to,w;}e[M<<1],q[M<<1];int head[N],total,hq[N],tot;void add(int u,int v,int w){e[++total]={head[u],u,v,w};head[u]=total;}void addq(int u,int v){tot++;q[tot].next=hq[u];q[tot].to=v;hq[u]=tot;}int rt[N];int find(int x){return rt[x]==x?x:(rt[x]=find(rt[x]));}
} using namespace klskr;namespace Tree_Chain_Partition{int fa[N],siz[N],depth[N],wson[N];int top[N],dfn[N],id[N],t;void dfs1(int x){depth[x]=depth[fa[x]]+1;siz[x]=1;for(int i=hq[x];i;i=q[i].next){int y=q[i].to;if(y==fa[x])  continue;fa[y]=x;dfs1(y);if(siz[y]>siz[wson[x]])  wson[x]=y;siz[x]+=siz[y];}}void dfs2(int x,int tp){top[x]=tp;dfn[x]=++t;id[t]=x;if(wson[x])  dfs2(wson[x],tp);for(int i=hq[x];i;i=q[i].next){int y=q[i].to;if(y==wson[x]||y==fa[x])  continue;dfs2(y,y);}}
} using namespace Tree_Chain_Partition;namespace Segment_Tree{struct Tree{int l,r,minn;#define l(i) tr[i].l#define r(i) tr[i].r#define ls(i) (i<<1)#define rs(i) (i<<1|1)#define minn(i) tr[i].minn}tr[N<<2];void build(int i,int l,int r){l(i)=l,r(i)=r;if(l==r){minn(i)=w[id[l]];return;}int mid=(l+r)>>1;build(ls(i),l,mid);build(rs(i),mid+1,r);minn(i)=min(minn(ls(i)),minn(rs(i)));return;}int query(int i,int ql,int qr){int l=l(i),r=r(i);if(ql<=l&&r<=qr)  return minn(i);int mid=(l+r)>>1,res=1e8;if(ql<=mid)  res=min(res,query(ls(i),ql,qr));if(mid<qr)  res=min(res,query(rs(i),ql,qr));return res;}
} using namespace Segment_Tree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read,m=read;for(int i=1;i<=(n<<1);i++)  rt[i]=i,w[i]=1e8;for(int i=1,a,b,c;i<=m;i++)  a=read,b=read,c=read,add(a,b,c),add(b,a,c);sort(e+1,e+total+1,[](EDGE a,EDGE b){return a.w>b.w;});for(int i=1;i<=total;i++){EDGE x=e[i];int u=x.from,v=x.to;int uu=find(u),vv=find(v);if(uu!=vv){rt[uu]=rt[vv]=++n;addq(n,uu);addq(uu,n);addq(n,vv),addq(vv,n);w[n]=x.w;}}for(int i=n;i>=1;i--){if(!dfn[i]){dfs1(i);dfs2(i,i);}}build(1,1,t);int T,u,v,ans;T=read;while(T-->0){u=read,v=read;int uu=find(u),vv=find(v);if(uu!=vv){puts("-1");continue;}ans=1e8;while(top[u]!=top[v]){if(depth[top[u]]<depth[top[v]])  swap(u,v);ans=min(ans,query(1,dfn[top[u]],dfn[u]));u=fa[top[u]];}ans=min(ans,(depth[u]<depth[v] ? query(1,dfn[u],dfn[v]) : query(1,dfn[v],dfn[u])));write(ans);pt;}return 0;
}

\(T_E\) 遥远的国度

涉及换根，那就换，我们"假装"换，(用一个变量 \(rt\) 存储当前的根，直接换)，但实际根仍为 \(1\)，树剖，线段树维护单点修改和区间最小值，单点修改不变，对于区间最小值:

  1. \(rt=u\) 查整棵树。
  2. \(rt\) 不在 \(u\) 子树里，该查啥查啥。
  3. \(rt\) 在 \(u\) 子树里，考虑将查询区间分成两段，设 \(v\) 为 \(u\) 在 \(rt\) 方向上的儿子，答案显然是总答案减去去 \(v\) 的子树的贡献，即分成 \([1,dfn[v]-1]\) 和 \([out[v]+1,t]\) 两段答案进行统计即可。

对于换根我们的大体思路就是这样。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define int long long
#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 100010
const int MAX=1e10;
int n,m,rt;
int w[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){ e[++total]={head[u],v}; head[u]=total;}namespace Tree_Chain_Partition{int fa[N],siz[N],wson[N],depth[N];int dfn[N],out[N],id[N],t,top[N];void dfs(int x){depth[x]=depth[fa[x]]+1;siz[x]=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x])  continue;fa[y]=x;dfs(y);if(siz[y]>siz[wson[x]])  wson[x]=y;siz[x]+=siz[y];}}void dfs(int x,int tp){top[x]=tp;dfn[x]=++t;id[t]=x;if(wson[x])  dfs(wson[x],tp);for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x]||y==wson[x])  continue;dfs(y,y);}out[x]=t;}
} using namespace Tree_Chain_Partition;namespace Segment_Tree{struct Tree{int l,r,minn,lazy;#define l(i) tr[i].l#define r(i) tr[i].r#define minn(i) tr[i].minn#define lazy(i) tr[i].lazy#define ls(i) (i<<1)#define rs(i) (i<<1|1)}tr[N<<2];void pushup(int i){minn(i)=min(minn(ls(i)),minn(rs(i)));}void pushdown(int i){if(!lazy(i)) return;minn(ls(i))=minn(rs(i))=lazy(ls(i))=lazy(rs(i))=lazy(i);lazy(i)=0;return;}void build(int i,int l,int r){l(i)=l,r(i)=r;if(l==r){minn(i)=w[id[l]];return;}int mid=(l+r)>>1;build(ls(i),l,mid);build(rs(i),mid+1,r);pushup(i);return;}void update(int i,int ul,int ur,int k){int l=l(i),r=r(i);if(ul<=l&&r<=ur){minn(i)=lazy(i)=k;return;}pushdown(i);int mid=(l+r)>>1;if(ul<=mid)  update(ls(i),ul,ur,k);if(mid<ur)  update(rs(i),ul,ur,k);pushup(i);return;}int query(int i,int ql,int qr){int l=l(i),r=r(i);if(ql<=l&&r<=qr){return minn(i);}pushdown(i);int mid=(l+r)>>1,res=MAX;if(ql<=mid)  res=min(res,query(ls(i),ql,qr));if(mid<qr)  res=min(res,query(rs(i),ql,qr));pushup(i);return res;}
} using namespace Segment_Tree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read,m=read;for(int a,b,i=1;i<n;i++){a=read,b=read;add(a,b),add(b,a);}for(int i=1;i<=n;i++)  w[i]=read;dfs(1);dfs(1,1);build(1,1,t);rt=read;int op,u,v,k,ans;while(m-->0){op=read;switch(op){case 1:rt=read;break;case 2:u=read,v=read,k=read;while(top[u]!=top[v]){if(depth[top[u]]<depth[top[v]])  swap(u,v);update(1,dfn[top[u]],dfn[u],k);u=fa[top[u]];}depth[u]<depth[v] ? update(1,dfn[u],dfn[v],k) : update(1,dfn[v],dfn[u],k);break;case 3:u=read;ans=MAX;if(u==rt)  ans=minn(1);else if(dfn[u]<dfn[rt]&&dfn[rt]<=out[u]){v=rt;while(top[u]!=top[v]){if(fa[top[v]]==u){v=top[v];break;}v=fa[top[v]];}if(fa[v]!=u)  v=wson[u];if(dfn[v]-1>=1)  ans=min(ans,query(1,1,dfn[v]-1));if(out[v]+1<=t)  ans=min(ans,query(1,out[v]+1,t));}elseans=query(1,dfn[u],out[u]);write(ans);pt;break;default:break;}}return 0;
}

对于换根，还可以求 \(LCA\)，比如 Jamie and Tree，我们可以分讨归纳证明，节点 \(u,v\) 在根为 \(rt\) 时的 \(LCA\) 为 \(lca(u,v),lca(u,rt),lca(v,rt)\) 中深度最大的节点，其他的按照上面的思路维护即可。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
const int N=1e5+10;
int n,q;
int w[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total,rt=1;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}namespace Tree_Chain_Partition{int fa[N],depth[N],siz[N],wson[N];int top[N],dfn[N],out[N],id[N],t;void dfs(int x){depth[x]=depth[fa[x]]+1;siz[x]=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x])  continue;fa[y]=x;dfs(y);if(siz[y]>siz[wson[x]])  wson[x]=y;siz[x]+=siz[y];}}void dfs(int x,int tp){top[x]=tp;dfn[x]=++t;id[t]=x;if(wson[x])  dfs(wson[x],tp);for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x]||y==wson[x])  continue;dfs(y,y);}out[x]=t;}int LCA(int u,int v){while(top[u]!=top[v]){if(depth[top[u]]<depth[top[v]])  swap(u,v);u=fa[top[u]];}return (depth[u]<depth[v] ? u : v);}int findson(int u,int rt){//查询u在rt方向上的儿子int v=rt;while(top[v]!=top[u]){if(fa[top[v]]==u){v=top[v];break;}v=fa[top[v]];}if(fa[v]!=u)  v=wson[u];return v;}
} using namespace Tree_Chain_Partition;namespace Segment_Tree{struct Tree{int l,r,sum,lazy;#define l(i) tr[i].l#define r(i) tr[i].r#define sum(i) tr[i].sum#define lazy(i) tr[i].lazy#define ls(i) (i<<1)#define rs(i) (i<<1|1)}tr[N<<2];void pushup(int i){sum(i)=sum(ls(i))+sum(rs(i));}void pushdown(int i){if(!lazy(i)) return;sum(ls(i))+=(r(ls(i))-l(ls(i))+1)*lazy(i);sum(rs(i))+=(r(rs(i))-l(rs(i))+1)*lazy(i);lazy(ls(i))+=lazy(i),lazy(rs(i))+=lazy(i);lazy(i)=0;return;}void build(int i,int l,int r){l(i)=l,r(i)=r;if(l==r){sum(i)=w[id[l]];return;}int mid=(l+r)>>1;build(ls(i),l,mid);build(rs(i),mid+1,r);pushup(i);return;}void update(int i,int ul,int ur,int k){int l=l(i),r=r(i);if(ul<=l&&r<=ur){lazy(i)+=k;sum(i)+=(r-l+1)*k;return;}pushdown(i);int mid=(l+r)>>1;if(ul<=mid)  update(ls(i),ul,ur,k);if(mid<ur)  update(rs(i),ul,ur,k);pushup(i);return;}int query(int i,int ql,int qr){int l=l(i),r=r(i);if(ql<=l&&r<=qr){return sum(i);}pushdown(i);int mid=(l+r)>>1,res=0;if(ql<=mid)  res+=query(ls(i),ql,qr);if(mid<qr)  res+=query(rs(i),ql,qr);pushup(i);return res;}
} using namespace Segment_Tree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read,q=read;for(int i=1;i<=n;i++)  w[i]=read;for(int a,b,i=1;i<n;i++){a=read,b=read;add(a,b),add(b,a);}dfs(1);dfs(1,1);build(1,1,t);int op,u,v,k,ans;int lca,lca1,lca2,lca3;while(q-->0){op=read;switch(op){case 1:rt=read;break;case 2:u=read,v=read,k=read;lca1=LCA(u,v);lca2=LCA(u,rt);lca3=LCA(v,rt);lca=(depth[lca1]>depth[lca2] ? lca1 : lca2);lca=(depth[lca]>depth[lca3] ? lca : lca3);if(lca==rt)update(1,1,t,k);else if(dfn[lca]<dfn[rt]&&dfn[rt]<=out[lca]){v=findson(lca,rt);if(dfn[v]-1>=1)  update(1,1,dfn[v]-1,k);if(out[v]+1<=t)  update(1,out[v]+1,t,k);}elseupdate(1,dfn[lca],out[lca],k);break;case 3:u=read;ans=0;if(u==rt){ans=query(1,1,t);}else if(dfn[u]<dfn[rt]&&dfn[rt]<=out[u]){v=findson(u,rt);if(dfn[v]-1>=1)  ans+=query(1,1,dfn[v]-1);if(out[v]+1<=t)  ans+=query(1,out[v]+1,t);}elseans=query(1,dfn[u],out[u]);write(ans),pt;break;default:break;}}return 0;
}

\(T_F\) 染色

思路差不多，多了点细节，线段树每个节点多维护一个 \(lc\) 和一个 \(rc\) 为每段左右端点的颜色，然后注意查完一段 \([dfn[top[u]],dfn[u]]\) 后，查一下 \(top[u]\) 和 \(fa[top[u]]\) 的颜色是否相同，相同就要让答案减一。

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
const int N=1e5+10;
#define M 400
int n,m;
int c[N];
struct EDGE{int next,to;}e[N<<1];
int head[N],total;
void add(int u,int v){e[++total]={head[u],v};head[u]=total;}namespace Tree_Chain_Partition{int fa[N],siz[N],depth[N],wson[N];int top[N],dfn[N],id[N],t;void dfs(int x){depth[x]=depth[fa[x]]+1;siz[x]=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x])  continue;fa[y]=x;dfs(y);if(siz[y]>siz[wson[x]])  wson[x]=y;siz[x]+=siz[y];}}void dfs(int x,int tp){top[x]=tp;dfn[x]=++t;id[t]=x;if(wson[x])  dfs(wson[x],tp);for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x]||y==wson[x])  continue;dfs(y,y);}}
} using namespace Tree_Chain_Partition;namespace Segment_Tree{struct Tree{int l,r,cnt,lc,rc,lazy;#define l(i) tr[i].l#define r(i) tr[i].r#define cnt(i) tr[i].cnt#define lc(i) tr[i].lc#define rc(i) tr[i].rc#define lazy(i) tr[i].lazy#define ls(i) (i<<1)#define rs(i) (i<<1|1)}tr[N<<2];void pushup(int i){lc(i)=lc(ls(i)),rc(i)=rc(rs(i));cnt(i)=cnt(ls(i))+cnt(rs(i));if(rc(ls(i))==lc(rs(i)))  --cnt(i);return;}void pushdown(int i){if(!lazy(i))  return;lazy(ls(i))=lazy(rs(i))=lazy(i);lc(ls(i))=rc(ls(i))=lazy(i);lc(rs(i))=rc(rs(i))=lazy(i);cnt(ls(i))=cnt(rs(i))=1;lazy(i)=0;return;}void build(int i,int l,int r){l(i)=l,r(i)=r;if(l==r){lc(i)=rc(i)=c[id[l]];cnt(i)=1;return;}int mid=(l+r)>>1;build(ls(i),l,mid);build(rs(i),mid+1,r);pushup(i);return;}void update(int i,int ul,int ur,int k){int l=l(i),r=r(i);if(ul<=l&&r<=ur){lazy(i)=k;lc(i)=rc(i)=k;cnt(i)=1;return;}pushdown(i);int mid=(l+r)>>1;if(ul<=mid)  update(ls(i),ul,ur,k);if(mid<ur)  update(rs(i),ul,ur,k);pushup(i);return;}int ask(int i,int x){int l=l(i),r=r(i);if(l==r)  return lc(i);pushdown(i);int mid=(l+r)>>1,res;if(x<=mid)  res=ask(ls(i),x);else  res=ask(rs(i),x);pushup(i);return res;}int query(int i,int ql,int qr){int l=l(i),r=r(i);if(ql<=l&&r<=qr){return cnt(i);}pushdown(i);int mid=(l+r)>>1,res=0;if(ql<=mid&&mid<qr){if(rc(ls(i))==lc(rs(i)))  res--;}if(ql<=mid)  res+=query(ls(i),ql,qr);if(mid<qr)  res+=query(rs(i),ql,qr);pushup(i);return res;}
} using namespace Segment_Tree;signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read,m=read;for(int i=1;i<=n;i++)  c[i]=read;for(int a,b,i=1;i<n;i++){a=read,b=read;add(a,b),add(b,a);}dfs(1),dfs(1,1);build(1,1,t);char op;int u,v,k,ans;while(m-->0){op=getchar();while(op!='Q'&&op!='C') op=getchar();u=read,v=read;if(op=='Q'){ans=0;while(top[u]!=top[v]){if(depth[top[u]]<depth[top[v]])  swap(u,v);ans+=query(1,dfn[top[u]],dfn[u]);u=top[u];int a=ask(1,dfn[u]),b=ask(1,dfn[fa[u]]);if(a==b)  ans--;u=fa[u];}ans+=(depth[u]<depth[v] ? query(1,dfn[u],dfn[v]) : query(1,dfn[v],dfn[u]));write(ans);pt;}if(op=='C'){k=read;while(top[u]!=top[v]){if(depth[top[u]]<depth[top[v]])  swap(u,v);update(1,dfn[top[u]],dfn[u],k);u=fa[top[u]];}depth[u]<depth[v] ? update(1,dfn[u],dfn[v],k) : update(1,dfn[v],dfn[u],k);}}return 0;
}

\(T_G\) 运输计划

二分答案树上差分，几个月前打 \(LCA\) 时就打了，当时倍增就被卡了，树剖跑飞快。

$$ my blog $$

$CODE$ 
#include<bits/stdc++.h>
using namespace std;
#define swap(x,y) (x^=y,y^=x,x^=y)
#define read read()
#define pt puts("")
inline int read{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
void write(int x){if(x<0)  putchar('-'),x=-x;if(x>9)  write(x/10);putchar(x%10+'0');return;
}
#define N 300010
int n,m;
int MAX;
struct EDGE{int next,to,t;}e[N<<1];
int head[N],total;
void add(int u,int v,int t){e[++total]={head[u],v,t};head[u]=total;}
int edge[N];
namespace Tree_Chain_Partition{int fa[N],siz[N],wson[N],depth[N];int top[N];int dis[N];void dfs1(int x){depth[x]=depth[fa[x]]+1;siz[x]=1;for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x])  continue;edge[y]=i;dis[y]=dis[x]+e[i].t;fa[y]=x;dfs1(y);if(siz[y]>siz[wson[x]])  wson[x]=y;siz[x]+=siz[y];}}void dfs2(int x,int tp){top[x]=tp;if(wson[x])  dfs2(wson[x],tp);for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==wson[x]||y==fa[x])  continue;dfs2(y,y);}}int LCA(int u,int v){while(top[u]!=top[v]){if(depth[top[u]]<depth[top[v]])  swap(u,v);u=fa[top[u]];}return (depth[u]<depth[v]?u:v);}
} using namespace Tree_Chain_Partition;
int u[N],v[N],lca[N],len[N];
int b[N];
int sum,reduce;
void dfs(int x){for(int i=head[x];i;i=e[i].next){int y=e[i].to;if(y==fa[x])  continue;dfs(y);b[x]+=b[y];}if(b[x]==sum)  reduce=max(reduce,e[edge[x]].t);
}
bool check(int x){for(int i=1;i<=n;i++)  b[i]=0;sum=reduce=0;for(int i=1;i<=m;i++){if(len[i]>x){sum++;b[u[i]]++;b[v[i]]++;b[lca[i]]-=2;}}dfs(1);if(MAX-reduce<=x)  return 1;return 0;
}int ans;
signed main()
{#ifndef ONLINE_JUDGEfreopen("lty.in","r",stdin);freopen("lty.out","w",stdout);#endifn=read,m=read;for(int a,b,c,i=1;i<n;i++){a=read,b=read,c=read;add(a,b,c),add(b,a,c);}dfs1(1),dfs2(1,1);for(int i=1;i<=m;i++){u[i]=read,v[i]=read;lca[i]=LCA(u[i],v[i]);len[i]=dis[u[i]]+dis[v[i]]-2*dis[lca[i]];MAX=max(MAX,len[i]);}int st=0,ed=MAX;while(st<ed){int mid=(st+ed)>>1;if(check(mid))ed=ans=mid;elsest=mid+1;}write(ans);return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/31943.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！

相关文章

[HDCTF 2023]YamiYami python中的另一种反序列化--yaml

[HDCTF 2023]YamiYami python中的另一种反序列化--yaml

今天做了到新颖的题，关于python中的yaml反序列化的题目，直接上题吧。发现第一个链接的参数是?url=XXXX,一眼利用点。嗯？直接出了flag，应该是非预期解。再看看有app.py，那就试试。发现app.*被过滤了，二次编码绕过试试。点击查看代码 @app.route(/) def index():session[p…
阅读更多...
offsetExplorer3.0 如何连接加SASL认证的zookeeper、kafka

offsetExplorer3.0 如何连接加SASL认证的zookeeper、kafka

offsetExplorer3.0连接速度与查看topic、consumers查询速度显著提升。建议使用offsetExplorer3.0代替旧版offsetExplorer offsetExplorer3.0下载地址：https://www.kafkatool.com/download.html 配置方式如下：
阅读更多...
msvc 获取c++类内存布局 /d1 reportAllClassLayout

msvc 获取c++类内存布局 /d1 reportAllClassLayout

visual studio 配置获取所有类内存布局 /d1 reportAllClassLayout 或者指定类 /d1 reportSingleClassLayoutXXXclass编译时输出： ps： https://www.openrce.org/articles/full_view/23【原文地址】https://blog.csdn.net/qq_29542611/article/details/79504396 VS2015 开发人员…
阅读更多...
TypeError报错处理

TypeError报错处理

哈喽，大家好，我是木头左！一、Python中的TypeError简介 这个错误通常表示在方法调用时，参数类型不正确，或者在对字符串进行格式化操作时，提供的变量与预期不符。 二、错误的源头：字符串格式化的奥秘 字符串格式化是Python中一个非常实用的功能，它允许根据一定的格式将变…
阅读更多...
双均线策略：量化交易中的黄金法则

双均线策略：量化交易中的黄金法则

在量化交易的世界里，双均线策略以其简单、高效而著称。这种策略利用两条不同周期的移动平均线（MA）来判断市场趋势，是许多交易者入门的不二选择。本文将深入探讨双均线策略的原理，并展示如何在聚宽平台上实现这一策略。 策略原理：双均线的动态平衡 双均线策略的核心在于比…
阅读更多...
E. We Need More Bosses

E. We Need More Bosses

原题链接 题解 1.已知如果两个点之间有两条边不重合的路径，那么这两个点就在一个边强连通分量里，所以我们可以把处于同一个边强连通分量的点缩起来 在这里，我忘记了怎么求边强连通分量，所以我再提醒一下自己 已知树结构是不存在强连通分量的，它的特性是深度大的节点只有一…
阅读更多...
Selenium4自动化测试8--控件获取数据--上传、下载、https和切换分页

Selenium4自动化测试8--控件获取数据--上传、下载、https和切换分页

10-上传 上传不能模拟用户在页面上选择本地文件，只能先把要上传的文件先准备好在代码里上传import time from selenium.webdriver.support.select import Select #pip install selenium from selenium import webdriver from selenium.webdriver.common.by import By# 定义一个…
阅读更多...
webase go-sdk 简单使用

webase go-sdk 简单使用

本流程在test目录下，其中用到的 solc-0.4.25 和 abigen 工具网上教程都比较详细，就暂时不展开聊，今天就大概描述流程。 1.将目录下的test.sol文件编译pragma solidity ^0.4.25;import "./Table.sol";contract test {string constant TABLE_NAME = "test2&quo…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 尧图建网站 广利置业