CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » jxm2001 » 长链剖分
2020-2021:teams:legal_string:jxm2001:长链剖分

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

后一修订版 		前一修订版
2020-2021:teams:legal_string:jxm2001:长链剖分 [2020/05/29 16:50]
jxm2001 创建 		2020-2021:teams:legal_string:jxm2001:长链剖分 [2020/07/27 22:54] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:长链剖分被移动至2020-2021:teams:legal_string:jxm2001:长链剖分
行 3: 行 3:
 ===== 算法简介 ===== ===== 算法简介 =====
  
-一种可以在线性时间复杂度维护子树中**深度有关的信息**的特殊算法。+一种可以在线性时间复杂度维护子树中**仅限深度有关的信息**的算法，主要用于一些特殊的 $\text{dp}$
  
-===== 算法思想 ====+===== 算法思想 ​=====
  
 +类似重链剖分，将儿子分为重儿子和轻儿子，重儿子组成的链构成长链
  
 +但不同的是重链剖分重儿子是子树结点最多的结点，长链剖分长儿子是子树深度最大的结点
  
-类似重链剖分，将儿子分为重儿子和轻儿子，也将链分为重链和轻链+长链剖分有两个重要性质
  
-但不同的是重链剖分重儿子是子树结点最多的结点，长链剖分重儿子是子树深度最大的结点+性质一：所有长链长度和为 $n$
  
-为了在$O\left(1\right)$+显然所有点均属于且仅属于一条长链，所以性质一成立
  
-为方便理解，先考虑点权树问题+性质二：长链剖分的一个重要性质是一个结点 $x$ 的 $k$ 级祖先所在的长链长度一定 $\ge k$
  
-使用 dfs 序可以把子树查询和修改问题转化区间修改问题，单次操作时间复杂度 ​$O\left(\log n\right)$+考虑结点 $x$ 和它的 $k$ 级祖先 $y$，如果 ​$x$ 和 $y$ 属于同一条长链，该情况下性质二成立
  
-因此重链剖分重点在如何解决树上路径修改问题，考虑将树划分成若干条链，分别对每条链进行修改、查询操作，便可实现树上路径修改+如果 $x$ 和 $y$ 不属于同一条长链，知 $y$ 的重儿子子树的深度一定大于 $x$ 的深度，该情况下性质二也成立
  
-为简化问题，先考虑根结点到某结点的路径，我们不希望看见该路径涉及成过多条链的情况，而将树划分成重路径和轻边可以很好地解决这一问题+===== 算法应用 =====
  
-首先给出重儿子和轻儿子的定义：对于非叶子节点，将所有儿子中以其为根的子树含结点数最多的儿子定义为重儿子，其余为轻儿子+==== 树上 $k$ 级祖先 ====
  
-父节点向重儿子连一条重边，每个轻儿子连一条轻边。若干重边组成一条重链+[[https://​www.luogu.com.cn/​problem/​P5903|洛谷p5903]]
  
-这样，根结点到某结点的路径便被划分成若干条轻边和重链相间的路径+先一遍 dfs 处理出每个结点的深度、父结点、重儿子，同时用倍增法 $O\left(n\log n\right)$ 时间处理出每个结点的 $2^k$ 级祖先
  
-易知每经过一条轻边，子树所含结点数减半，因此一条路径最多经过 ​$\log n$ 条轻边+第二遍 dfs 处理出每个结点所在长链的起点 ​$x$
  
-因此单次修改或查询根结点到某结点的路径的时间复杂度变为 ​$O\left(\log^2 n\right)$+对每个长链的起点 $x$ ，暴力处理出 $x$ 上下 $\text{len}(x)$ 个结点，其中 ​$\text{len}(x)$ 表示 $x$ 所在长链的长度
  
-而对于端点为两个非根结点的路径，可以考虑像倍增法求 ​$\text{LCA}$ 那样不断把两个结点往上提，直到两个结点位于同一条链+由于所有长链长度之和为 $n$ ，所以该暴力处理的时间复杂度为 ​$O\left(n\right)$
  
-===== 代码实现 =====+对每次查询结点 $x$ 的 $k$ 级祖先，记 $h_k=\lfloor \log_2 k\rfloor$，$tk=k-2^{h_k}$ ​
  
-先一遍 dfs 处理出每个结点的深度、父结点、重儿子+先从 $x$ 向上跳 $2^{h_k}$ 级到 $y$ ， 根据长链剖分性质，知 $y$ 所在长链长度必然 $\ge 2^{h_k}$
  
-第二遍 dfs 确定 dfs 序和每条链的起点，注意 dfs 要先重儿子，再轻儿子，确保重链上 dfs 序连续+此时还需向上跳 $tk$ 级，$tk\lt 2^{h_k}$，所以 $x$ 的 $k$ 级祖先一定在 $y$ 所在长链起点的上下 $\text{len}(x)$ 级结点范围内
  
-路径上查询和修改操作需要每次选择路径两端点中所在链的顶端结点的深度较大的结点，线段树查询/​修改后跳到所在链的顶端结点的父结点+因此在从 $y$ 跳到 ​$y$ 所在长链起点，最后便可以 $O\left(1\right)$ 访问目标结点
  
-===== 代码模板 ===== +时间复杂度 ​$O\left(n\log n\right)-O\left(1\right)$
- +
-[[https://​www.luogu.com.cn/​problem/​P3384|洛谷p3384]] +
- +
-模板题 +
- +
-题目大意是说给定一棵 ​$n$ 个结点的点权树，每次操作为查询路径或子树上的权值和，或者给路径或子树上的每个点权值加 $v$ ，所有结果取模+
  
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-#include <​cstdio>​ +const int MAXN=5e5+5,MAXM=21; 
-#include <​cstdlib>​ +unsigned int s; 
-#include <​algorithm>​ +inline ​unsigned ​int get(unsigned int x){ 
-#include <​cctype>​ + x^=x<<13; 
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) + x^=x>>17; 
-#define _rep(i,a,b) for(int i=(a);i<​=(b);​++i) + x^=x<<5; 
-using namespace std; + return ​s=x;
-typedef long long LL; +
-inline int read_int(){ +
- int t=0;bool sign=false;​char c=getchar(); +
- while(!isdigit(c)){sign|=c=='​-'​;c=getchar();​} +
- while(isdigit(c)){t=(t<<1)+(t<<​3)+(c&​15);c=getchar();​} +
- return ​sign?-t:t;+
 } }
-inline LL read_LL(){ 
- LL t=0;bool sign=false;​char c=getchar();​ 
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} 
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} 
- return sign?-t:t; 
-} 
-inline void write(LL x){ 
- register char c[21],​len=0;​ 
- if(!x)return putchar('​0'​),​void();​ 
- if(x<​0)x=-x,​putchar('​-'​);​ 
- while(x)c[++len]=x%10,​x/​=10;​ 
- while(len)putchar(c[len--]+48);​ 
-} 
-inline void space(LL x){write(x),​putchar('​ ');} 
-inline void enter(LL x){write(x),​putchar('​\n'​);​} 
-const int MAXN=1e5+5; 
-int mod; 
-struct Tree{ 
- LL a[MAXN<<​2],​sum[MAXN<<​2],​lazy[MAXN<<​2];​ 
- int lef[MAXN<<​2],​rig[MAXN<<​2];​ 
- void init(int n,int *w){ 
- _rep(i,​1,​n) 
- a[i]=w[i];​ 
- build(1,​1,​n);​ 
- } 
- void push_up(int k){ 
- sum[k]=(sum[k<<​1]+sum[k<<​1|1])%mod;​ 
- } 
- void build(int k,int L,int R){ 
- lef[k]=L,​rig[k]=R;​ 
- int M=L+R>>​1;​ 
- if(L==R) 
- return sum[k]=a[M],​void();​ 
- build(k<<​1,​L,​M);​ 
- build(k<<​1|1,​M+1,​R);​ 
- push_up(k);​ 
- } 
- void push_down(int k){ 
- if(lazy[k]){ 
- int lson=k<<​1,​rson=k<<​1|1;​ 
- lazy[lson]=(lazy[lson]+lazy[k])%mod;​ 
- sum[lson]=(sum[lson]+lazy[k]*(rig[lson]-lef[lson]+1))%mod;​ 
- lazy[rson]=(lazy[rson]+lazy[k])%mod;​ 
- sum[rson]=(sum[rson]+lazy[k]*(rig[rson]-lef[rson]+1))%mod;​ 
- lazy[k]=0;​ 
- } 
- } 
- LL query(int k,int L,int R){ 
- if(L<​=lef[k]&&​rig[k]<​=R) 
- return sum[k]; 
- push_down(k);​ 
- int mid=lef[k]+rig[k]>>​1;​ 
- if(mid>​=R) 
- return query(k<<​1,​L,​R);​ 
- else if(mid<​L) 
- return query(k<<​1|1,​L,​R);​ 
- else 
- return (query(k<<​1,​L,​R)+query(k<<​1|1,​L,​R))%mod;​ 
- } 
- void update(int k,int L,int R,LL v){ 
- if(L<​=lef[k]&&​rig[k]<​=R){ 
- sum[k]=(sum[k]+(rig[k]-lef[k]+1)*v)%mod;​ 
- lazy[k]=(lazy[k]+v)%mod;​ 
- return; 
- } 
- push_down(k);​ 
- int mid=lef[k]+rig[k]>>​1;​ 
- if(mid>​=L) 
- update(k<<​1,​L,​R,​v);​ 
- if(mid<​R) 
- update(k<<​1|1,​L,​R,​v);​ 
- push_up(k);​ 
- } 
-}tree; 
 struct Edge{ struct Edge{
  int to,next;  int to,next;
行 150: 行 66:
  head[u]=m;  head[u]=m;
 } }
-int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],​dfs_id[MAXN],​dfs_t; +int d[MAXN],fa[MAXN][MAXM],log_2[MAXN]; 
-int h_son[MAXN],​mson[MAXN],​p[MAXN],​dfs_w[MAXN]; +int h_son[MAXN],​mson[MAXN],​p[MAXN]; 
-void dfs_1(int u,int fa,int depth){ +vector<​int>​ Node_up[MAXN],Node_down[MAXN]; 
- sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;+void get_log2(){ 
 + log_2[0]=-1;​ 
 + _for(i,​1,​MAXN) 
 + log_2[i]=log_2[i>>​1]+1;​ 
 +} 
 +void dfs_1(int u,int depth){ 
 + mson[u]=d[u]=depth; 
 + _rep(i,​1,​log_2[d[u]]) 
 + fa[u][i]=fa[fa[u][i-1]][i-1];
  for(int i=head[u];​i;​i=edge[i].next){  for(int i=head[u];​i;​i=edge[i].next){
  int v=edge[i].to;​  int v=edge[i].to;​
- if(v==fa) + dfs_1(v,​depth+1);​ 
- continue;​ + if(mson[v]>​mson[u]){
- dfs_1(v,u,depth+1); +
- sz[u]+=sz[v]; +
- if(sz[v]>​mson[u]){+
  h_son[u]=v;​  h_son[u]=v;​
- mson[u]=sz[v];+ mson[u]=mson[v];
  }  }
  }  }
 } }
 void dfs_2(int u,int top){ void dfs_2(int u,int top){
- dfs_id[u]=++dfs_t;p[u]=top;dfs_w[dfs_t]=w[u]; + p[u]=top; 
- if(mson[u])+ if(u==top){ 
 + for(int i=0,​pos=u;​i<​=mson[u]-d[u];​pos=fa[pos][0],​i++) 
 + Node_up[u].push_back(pos);​ 
 + for(int i=0,pos=u;i<=mson[u]-d[u];pos=h_son[pos],​i++) 
 + Node_down[u].push_back(pos); 
 + } 
 + if(h_son[u])
  dfs_2(h_son[u],​top);​  dfs_2(h_son[u],​top);​
  for(int i=head[u];​i;​i=edge[i].next){  for(int i=head[u];​i;​i=edge[i].next){
  int v=edge[i].to;​  int v=edge[i].to;​
- if(v==f[u]||v==h_son[u])+ if(v==h_son[u])
  continue;  continue;
  dfs_2(v,​v);​  dfs_2(v,​v);​
  }  }
 } }
-LL query_son(int u){return tree.query(1,​dfs_id[u],​dfs_id[u]+sz[u]-1);​} +int query(int u,int k){ 
-void update_son(int u,int w){tree.update(1,​dfs_id[u],​dfs_id[u]+sz[u]-1,​w);​} + if(!k)return ​u; 
-LL query_path(int u,int v){ + u=fa[u][log_2[k]],k-=1<<​log_2[k]; 
- LL ans=0; + k-=d[u]-d[p[u]],​u=p[u];​ 
- while(p[u]!=p[v]){ + return k>​=0?​Node_up[u][k]:Node_down[u][-k];
- if(d[p[u]]<​d[p[v]]) +
- swap(u,v); +
- ans=(ans+tree.query(1,​dfs_id[p[u]],dfs_id[u]))%mod; +
- u=f[p[u]]; +
- } +
- if(d[u]>​d[v]) +
- swap(u,v); +
- ans=(ans+tree.query(1,dfs_id[u],​dfs_id[v]))%mod; +
- return ans; +
-} +
-void update_path(int u,int v,int w){ +
- while(p[u]!=p[v]){ +
- if(d[p[u]]<d[p[v]]) +
- swap(u,​v);​ +
- tree.update(1,​dfs_id[p[u]],dfs_id[u],​w);​ +
- u=f[p[u]]; +
- } +
- if(d[u]>d[v]) +
- swap(u,​v);​ +
- tree.update(1,​dfs_id[u],dfs_id[v],w);+
 } }
 int main() int main()
 { {
- int n=read_int(),q=read_int(),root=read_int(),​opt,x,y,z; + int n,​q,​root,​x,​y;​ 
- mod=read_int(); + cin>>​n>>​q>>​s; 
- _rep(i,​1,​n) + _rep(i,​1,​n){ 
- w[i]=read_LL()%mod; + fa[i][0]=read_int(); 
- _for(i,1,n){ + if(fa[i][0]) 
- x=read_int(),y=read_int(); + Insert(fa[i][0],i); 
- Insert(x,​y);​ + else 
- Insert(y,x);+ root=i;
  }  }
- dfs_1(root,-1,0);+ get_log2();​ 
 + dfs_1(root,​0);​
  dfs_2(root,​root);​  dfs_2(root,​root);​
- tree.init(n,dfs_w); + long long tot=0,last=0; 
- while(q--){ + int u,k; 
- opt=read_int(); + _rep(i,1,q){ 
- if(opt==1){ + u=(get(s)^last)%n+1; 
- x=read_int();​y=read_int();​z=read_int();​ + k=(get(s)^last)%(d[u]+1); 
- update_path(x,​y,​z); + last=query(u,k); 
- } + tot^=last*i;
- else if(opt==2){ +
- x=read_int();​y=read_int(); +
- enter(query_path(x,​y)); +
- } +
- else if(opt==3){ +
- x=read_int();​y=read_int();​ +
- update_son(x,y); +
- } +
- else +
- enter(query_son(read_int()));+
  }  }
 + enter(tot);​
  return 0;  return 0;
 } }
行 239: 行 138:
 </​hidden>​ </​hidden>​
  
-===== 算法习题 =====+==== 合并信息 ​====
  
-=== 习题一 ===+[[https://​www.luogu.com.cn/​problem/​P5904|洛谷p5904]]
  
-[[https://​www.luogu.com.cn/​problem/​P3038|洛谷p3038]]+给定一棵 $n$ 个结点的树，问有多少个无序点对 $(i,j,k)$ 满足 $i,j,k$ 两两间距离相等
  
-给出一棵 $n$ 个结点的边权树，初始边权全为 $0$ ，有 ​$m$ 个操作，操作为将一条路径上的边权加一或询问某条边的权值+树形$\text{dp}$，状态转移方程可以参考这份博客[[https://​www.luogu.com.cn/​blog/​xht37/​solution-p3565|详情]]
  
-考虑一个点有唯一的父结点，因此可以把该点与父结点的连边的边权作为该点的点权。根结点权值任意，不影响结果+利用指针位移使得父结点以 ​$O(1)$ 时间继承重儿子信息，暴力继承轻儿子信息
  
-而路径修改/​查询注意跳过 ​$\text{LCA}$ 即可+设当前结点为 ​$u$，$u$ 的儿子结点为 $x$，每次暴力继承时间复杂度为 $O\left(\text{len}\left(x\right)\right)$
  
-<hidden 查看代码>​ +总时间复杂度为 $\sum_u\left(\left(\sum_x \text{len}\left(x\right)\right)-\text{len}\left(u\right)+1\right)$
-<code cpp> +
-#include <​cstdio>​ +
-#include <​cstdlib>​ +
-#include <​algorithm>​ +
-#include <​cctype>​ +
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) +
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) +
-using namespace std; +
-typedef long long LL; +
-inline int read_int(){ +
- int t=0;bool sign=false;​char c=getchar();​ +
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
- return sign?​-t:​t;​ +
-} +
-inline char get_char(){ +
- char c=getchar();​ +
- while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ +
- return c; +
-} +
-inline void write(LL x){ +
- register char c[21],len=0; +
- if(!x)return putchar('​0'​),​void();​ +
- if(x<​0)x=-x,​putchar('​-'​);​ +
- while(x)c[++len]=x%10,​x/​=10;​ +
- while(len)putchar(c[len--]+48);​ +
-} +
-inline void space(LL x){write(x),​putchar('​ ');} +
-inline void enter(LL x){write(x),​putchar('​\n');} +
-const int MAXN=1e5+5;​ +
-#define lowbit(x) ((x)&(-x)) +
-struct Tree{ +
- LL c[2][MAXN],​n;​ +
- void add(int pos,int v){ +
- int k=pos; +
- while(pos<​=n){ +
- c[0][pos]+=v;​ +
- c[1][pos]+=v*(k-1);​ +
- pos+=lowbit(pos);​ +
- } +
- } +
- void update(int lef,int rig,int v){ +
- add(lef,​v);​ +
- add(rig+1,​-v);​ +
- } +
- LL sum(int pos){ +
- int k=pos; +
- LL ans1=0,​ans2=0;​ +
- while(pos){ +
- ans1+=c[0][pos];​ +
- ans2+=c[1][pos];​ +
- pos-=lowbit(pos);​ +
- } +
- return ans1*k-ans2;​ +
- } +
- int query(int lef,int rig){ +
- return sum(rig)-sum(lef-1);​ +
- } +
-}tree; +
-struct Edge{ +
- int to,next; +
-}edge[MAXN<<​1];​ +
-int head[MAXN],​m;​ +
-void Insert(int ​u,int v){ +
- edge[++m].to=v; +
- edge[m].next=head[u];​ +
- head[u]=m;​ +
-} +
-int d[MAXN],​w[MAXN],​sz[MAXN],​f[MAXN],​dfs_id[MAXN],​dfs_t;​ +
-int h_son[MAXN],​mson[MAXN],​p[MAXN],​dfs_w[MAXN];​ +
-void dfs_1(int u,int fa,int depth){ +
- sz[u]=1;​f[u]=fa;​d[u]=depth;​mson[u]=0;​ +
- for(int i=head[u];​i;​i=edge[i].next){ +
- int v=edge[i].to;​ +
- if(v==fa) +
- continue;​ +
- dfs_1(v,​u,​depth+1);​ +
- sz[u]+=sz[v];​ +
- if(sz[v]>​mson[u]){ +
- h_son[u]=v;​ +
- mson[u]=sz[v];​ +
- } +
- } +
-} +
-void dfs_2(int u,int top){ +
- dfs_id[u]=++dfs_t;​p[u]=top;​dfs_w[dfs_t]=w[u];​ +
- if(mson[u]) +
- dfs_2(h_son[u],​top);​ +
- for(int i=head[u];​i;​i=edge[i].next){ +
- int v=edge[i].to;​ +
- if(v==f[u]||v==h_son[u]) +
- continue;​ +
- dfs_2(v,​v);​ +
- } +
-} +
-//LL query_son(int u){return tree.query(dfs_id[u]+1,​dfs_id[u]+sz[u]-1);​} +
-//void update_son(int u,int w){tree.update(dfs_id[u]+1,​dfs_id[u]+sz[u]-1,​w);​} +
-LL query_path(int u,int v){ +
- LL ans=0; +
- while(p[u]!=p[v]){ +
- if(d[p[u]]<​d[p[v]]) +
- swap(u,​v);​ +
- ans+=tree.query(dfs_id[p[u]],​dfs_id[u]);​ +
- u=f[p[u]];​ +
- } +
- if(d[u]>​d[v]) +
- swap(u,​v);​ +
- ans+=tree.query(dfs_id[u]+1,​dfs_id[v]);​ +
- return ans; +
-} +
-void update_path(int u,int v,int w){ +
- while(p[u]!=p[v]){ +
- if(d[p[u]]<​d[p[v]]) +
- swap(u,​v);​ +
- tree.update(dfs_id[p[u]],​dfs_id[u],​w);​ +
- u=f[p[u]];​ +
- } +
- if(d[u]>​d[v]) +
- swap(u,​v);​ +
- tree.update(dfs_id[u]+1,​dfs_id[v],​w);​ +
-} +
-int main() +
-{ +
- int n=read_int(),​q=read_int(),​root=1,​x,​y;​ +
- char opt; +
- tree.n=n;​ +
- _for(i,​1,​n){ +
- x=read_int(),​y=read_int();​ +
- Insert(x,​y);​ +
- Insert(y,​x);​ +
- } +
- dfs_1(root,​-1,​0);​ +
- dfs_2(root,​root);​ +
- while(q--){ +
- opt=get_char();​ +
- x=read_int(),​y=read_int();​ +
- if(opt=='​P'​) +
- update_path(x,​y,​1);​ +
- else +
- enter(query_path(x,​y));​ +
- } +
- return 0; +
-} +
-</​code>​ +
-</​hidden>​+
  
-=== 习题二 ===+每个结点仅在 $\sum_u\left(\left(\sum_x \text{len}\left(x\right)\right)\right)$ 作为它的父结点的子结点出现一次
  
-[[https://​www.luogu.com.cn/​problem/​P2486|洛谷p2486]]+所以有 $\sum_u\left(\left(\sum_x \text{len}\left(x\right)\right)\right)=\sum_u \text{len}\left(u\right)-\text{len}(root)$
  
-给定一棵个 $n$ 节点的点权树，共有 $m$ 个操作，操作分为两种： +所以总时间复杂度为 $O\left(n\right)$
- +
-1.将 $a$ 节点到节点 $b$ 的路径上的所有点(包括 $a$ 和 $b$ )都染成颜色 ​$c$ +
- +
-2.询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量(颜色段的定义是极长的连续相同颜色被认为是一段) +
- +
-一道很好的重链剖分练手题，这里仅给出代码+
  
 <hidden 查看代码>​ <hidden 查看代码>​
 <code cpp> <code cpp>
-#include <​cstdio>​ +const int MAXN=5e5+5;
-#include <​algorithm>​ +
-#include <​cstring>​ +
-#include <​cctype>​ +
-#define _for(i,a,b) for(int i=(a);​i<​(b);​++i) +
-#define _rep(i,a,b) for(int i=(a);​i<​=(b);​++i) +
-using namespace std; +
-typedef long long LL; +
-inline int read_int(){ +
- int t=0;bool sign=false;​char c=getchar();​ +
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
- return sign?​-t:​t;​ +
-} +
-inline LL read_LL(){ +
- LL t=0;bool sign=false;​char c=getchar();​ +
- while(!isdigit(c)){sign|=c=='​-';​c=getchar();​} +
- while(isdigit(c)){t=(t<<​1)+(t<<​3)+(c&​15);​c=getchar();​} +
- return sign?​-t:​t;​ +
-} +
-inline char get_char(){ +
- char c=getchar();​ +
- while(c=='​ '​||c=='​\n'​||c=='​\r'​)c=getchar();​ +
- return c; +
-} +
-inline void write(LL x){ +
- register char c[21],​len=0;​ +
- if(!x)return putchar('​0'​),​void();​ +
- if(x<​0)x=-x,​putchar('​-'​);​ +
- while(x)c[++len]=x%10,​x/​=10;​ +
- while(len)putchar(c[len--]+48);​ +
-} +
-inline void space(LL x){write(x),​putchar('​ ');} +
-inline void enter(LL x){write(x),​putchar('​\n'​);​} +
-const int MAXN=1e5+5; +
-int lef_color,​rig_color;​ +
-struct Tree{ +
- int a[MAXN<<​2],​lazy[MAXN<<​2],​lc[MAXN<<​2],​rc[MAXN<<​2],​sum[MAXN<<​2];​ +
- int lef[MAXN<<​2],​rig[MAXN<<​2];​ +
- void init(int n,int *w){ +
- _rep(i,​1,​n) +
- a[i]=w[i];​ +
- build(1,​1,​n);​ +
- } +
- void push_up(int k){ +
- sum[k]=sum[k<<​1]+sum[k<<​1|1];​ +
- lc[k]=lc[k<<​1];​ +
- rc[k]=rc[k<<​1|1];​ +
- if(rc[k<<​1]==lc[k<<​1|1]) +
- sum[k]--;​ +
- } +
- void build(int k,int L,int R){ +
- lef[k]=L,​rig[k]=R;​ +
- int M=L+R>>​1;​ +
- if(L==R){ +
- sum[k]=1;​ +
- lc[k]=rc[k]=a[M];​ +
- return;​ +
- } +
- build(k<<​1,​L,​M);​ +
- build(k<<​1|1,​M+1,​R);​ +
- push_up(k);​ +
- } +
- void push_lazy(int k,int lz){ +
- lazy[k]=lc[k]=rc[k]=lz;​ +
- sum[k]=1;​ +
- } +
- void push_down(int k){ +
- if(lazy[k]){ +
- push_lazy(k<<​1,​lazy[k]);​ +
- push_lazy(k<<​1|1,​lazy[k]);​ +
- lazy[k]=0;​ +
- } +
- } +
- int query(int k,int L,int R){ +
- if(L<​=lef[k]&&​rig[k]<​=R){ +
- if(lef[k]==L) +
- lef_color=lc[k];​ +
- if(rig[k]==R) +
- rig_color=rc[k];​ +
- return sum[k]; +
- } +
- push_down(k);​ +
- int mid=lef[k]+rig[k]>>​1;​ +
- if(mid>​=R) +
- return query(k<<​1,​L,​R);​ +
- else if(mid<​L) +
- return query(k<<​1|1,​L,​R);​ +
- else{ +
- if(rc[k<<​1]==lc[k<<​1|1]) +
- return query(k<<​1,​L,​R)+query(k<<​1|1,​L,​R)-1;​ +
- else +
- return query(k<<​1,​L,​R)+query(k<<​1|1,​L,​R);​ +
- } +
- } +
- void update(int k,int L,int R,int c){ +
- if(L<​=lef[k]&&​rig[k]<​=R){ +
- push_lazy(k,​c);​ +
- return;​ +
- } +
- push_down(k);​ +
- int mid=lef[k]+rig[k]>>​1;​ +
- if(mid>​=L) +
- update(k<<​1,​L,​R,​c);​ +
- if(mid<​R) +
- update(k<<​1|1,​L,​R,​c);​ +
- push_up(k);​ +
- } +
-}tree;+
 struct Edge{ struct Edge{
  int to,next;  int to,next;
行 530: 行 170:
  head[u]=m;  head[u]=m;
 } }
-int d[MAXN],w[MAXN],sz[MAXN],f[MAXN],dfs_id[MAXN],dfs_t; +int d[MAXN],Son[MAXN],len[MAXN]; 
-int h_son[MAXN],mson[MAXN],p[MAXN],dfs_w[MAXN]; +LL *f[MAXN],*g[MAXN],dp[MAXN<<​2],​*pos=dp,​ans; 
-void dfs_1(int u,int fa,int depth){ +void Malloc(int u){ 
- sz[u]=1;​f[u]=fa;​d[u]=depth;mson[u]=0;+ f[u]=pos,pos+=len[u]<<​1;​ 
 + g[u]=pos,pos+=len[u]<<1; 
 +} 
 +void dfs_1(int u,int depth,int fa){ 
 + d[u]=depth;​Son[u]=0;
  for(int i=head[u];​i;​i=edge[i].next){  for(int i=head[u];​i;​i=edge[i].next){
  int v=edge[i].to;​  int v=edge[i].to;​
  if(v==fa)  if(v==fa)
  continue;  continue;
- dfs_1(v,u,depth+1); + dfs_1(v,​depth+1,u); 
- sz[u]+=sz[v]; + if(len[v]>len[Son[u]]) 
- if(sz[v]>mson[u]){ + Son[u]=v;
- h_son[u]=v; +
- mson[u]=sz[v];​ +
- }+
  }  }
 + len[u]=len[Son[u]]+1;​
 } }
-void dfs_2(int u,int top){ +void dfs_2(int u,int fa){ 
- dfs_id[u]=++dfs_t;p[u]=top;dfs_w[dfs_t]=w[u]; + if(Son[u]){ 
- if(mson[u]) + f[Son[u]]=f[u]+1,​g[Son[u]]=g[u]-1; 
- dfs_2(h_son[u],top);+ dfs_2(Son[u],u); 
 + } 
 + f[u][0]=1,ans+=g[u][0];
  for(int i=head[u];​i;​i=edge[i].next){  for(int i=head[u];​i;​i=edge[i].next){
  int v=edge[i].to;​  int v=edge[i].to;​
- if(v==f[u]||v==h_son[u])+ if(v==fa||v==Son[u])
  continue;  continue;
- dfs_2(v,v); + Malloc(v);​ 
- } + dfs_2(v,u); 
-} + _for(i,0,len[v]){ 
-int query_path(int u,int v){ + if(i) ans+=f[u][i-1]*g[v][i]; 
- int c1=-1,​c2=-1,​ans=0; + ans+=g[u][i+1]*f[v][i]; 
- while(p[u]!=p[v]){ + } 
- if(d[p[u]]<d[p[v]]){ + _for(i,0,len[v]){ 
- swap(u,v); + g[u][i+1]+=f[u][i+1]*f[v][i]; 
- swap(c1,c2);+ if(i) g[u][i-1]+=g[v][i]; 
 + f[u][i+1]+=f[v][i];
  }  }
- ans+=tree.query(1,​dfs_id[p[u]],​dfs_id[u]);​ 
- if(c1==rig_color) 
- ans--; 
- c1=lef_color;​ 
- u=f[p[u]];​ 
  }  }
- if(d[u]>​d[v]){ 
- swap(u,​v);​ 
- swap(c1,​c2);​ 
- } 
- ans+=tree.query(1,​dfs_id[u],​dfs_id[v]);​ 
- if(c1==lef_color) 
- ans--; 
- if(rig_color==c2) 
- ans--; 
- return ans; 
-} 
-void update_path(int u,int v,int w){ 
- while(p[u]!=p[v]){ 
- if(d[p[u]]<​d[p[v]]) 
- swap(u,​v);​ 
- tree.update(1,​dfs_id[p[u]],​dfs_id[u],​w);​ 
- u=f[p[u]];​ 
- } 
- if(d[u]>​d[v]) 
- swap(u,v); 
- tree.update(1,​dfs_id[u],​dfs_id[v],​w);​ 
 } }
 int main() int main()
 { {
- int n=read_int(),​q=read_int(),root=1,x,y; + int n=read_int(),​u,v,root=1;
- char opt; +
- _rep(i,​1,​n) +
- w[i]=read_int();+
  _for(i,​1,​n){  _for(i,​1,​n){
- x=read_int(),y=read_int();​ + u=read_int();v=read_int();​ 
- Insert(x,y); + Insert(u,v); 
- Insert(y,x); + Insert(v,u);
- } +
- dfs_1(root,​-1,​0);​ +
- dfs_2(root,​root);​ +
- tree.init(n,​dfs_w);​ +
- while(q--){ +
- opt=get_char();​ +
- x=read_int();​y=read_int();​ +
- if(opt=='​C'​) +
- update_path(x,​y,​read_int());​ +
- else +
- enter(query_path(x,​y));+
  }  }
 + dfs_1(root,​0,​0);​
 + Malloc(root);​
 + dfs_2(root,​0);​
 + enter(ans);​
  return 0;  return 0;
 } }
2020-2021/teams/legal_string/jxm2001/长链剖分.1590742237.txt.gz · 最后更改: 2020/05/29 16:50 由 jxm2001

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3