树剖板子题单 log 做法
murder_drones
·
·
题解
我觉得不会有人无聊到写这个长达 6KB 还比树剖慢的东西，除了我。
这篇题解不是树剖题解。
想要给这题一个 1log 的做法，但是不会 Top Tree，所以对子树处理取了个巧。
考虑贡献可拆成链对链，链对子树，子树对链，子树对子树。链又可以被容斥成两点到根，lca 及其父亲到根四条根链，故而下文只考虑根链（有四倍常数）。
$acc_u$：u 的祖先。
$tag_u$：u 处修改贡献之和，不同贡献对的 $tag$ 相互独立。
## 子树对子树
最简单的部分。处理出 dfn 序和子树大小然后上树状数组区间加区间求和即可。
具体地，一个点的子树在 dfn 序上的范围是 $[dfn_x,dfn_x+sz_x-1]$，我们把两种操作都对应成了区间操作，这里和树剖是类似的。
## 根链对子树
如上图左，则点 $u$ 的答案为：
$$\sum_{x \in sub_u} (dep_x-dep_u+1)tag_x$$
$$=({\sum_{x \in sub_u} (dep_x+1)tag_x})-dep_u({\sum_{x \in sub_u} tag_x})$$
上 dfn 树状数组单点加子树查维护括号里两个东西即可。
## 子树对根链
如上图右，与第二种情况相反。
$$\sum_{x \in acc_u} (dep_u-dep_x+1)tag_x$$
$$=dep_u({\sum_{x \in acc_u} tag_x})-({\sum_{x \in acc_u} (dep_x-1)tag_x})$$
这里是子树加单点查。
## 链对链
[全局平衡二叉树](https://oi-wiki.org/ds/global-bst/)的优势区间，直接上就是。
## 全局平衡二叉树
大致讲一下吧。我们想想链剖为什么复杂度会多一只 log，它跳重链要跳 log 次，每次查询要 log。前者不好省略，我们考虑让后者去迎合前者。
我们先做一个小优化：原本线段树是大家用一棵，我们给他改成一条每条重链开一棵。但是这并没有解决时间复杂度的问题，~~而且成功在子树问题方面获得了劣势~~。
为啥还是不好呢？我们看图：
这个 6 号点到根的路径过了七层线段树节点，可是 5 号点只过了三层，这就不平衡了，不利于时间复杂度。
接下来，我们要让这些线段树变成全局平衡的形式。全局平衡，说白了就是你这棵线段树不要只顾着自己平衡，而是要往远了看，底下可能深的就浅一点，底下可能浅的就深一点。
具体地，我们每次以**轻子树加自己的大小总和**为权（$=sz_u-sz_{wson_u}$），求出线段树区间内的加权中点（lower_bound$(\frac{sum+1}{2})$）作为这个线段树节点的 mid。(细节：由于线段树和平衡树不一样，当 mid 取到右端点的时候要让他减一。)
效果好不好呢？我们还是看图。
可以看到，全局平衡后在底下深的就浅了。6 号点仅需要爬六层，5 号点却要爬四层了。
每次的操作是重链的一段前缀。以 9 号点为例，其需要计入答案的节点用绿色圈出，会经过但不算答案的点用蓝色圈出。（去原树看看也确实是 1,2,3,9 在其到根路径上。）
大致分析一下复杂度，在你跳到根的过程中，首先轻边只会经过 log 条，这是重剖所保证的性质。那重边（线段树的边）呢？往上跳一步，他的轻重子树大小之和是要翻倍的（因为取的是带权中点，最大的一边尽可能小）。虽然有可能出现某个点轻子树非常非常大导致翻倍失败的情况，但这不影响复杂度，仅仅是一个常数（我不会分析）。那么重边也只会跳 $O(\log)$ 条（注意和轻边的严格 log 相区分）。那么时间复杂度就是 $O(\log)$ 的。
~~我的全局平衡二叉树喜欢用线段树形式，但貌似主流都是平衡树形式的样子。~~
于是我们获得了 $O(n\log n)$ 时间复杂度的做法。但是全局平衡二叉树常数太大了。[最慢 381ms](https://www.luogu.com.cn/record/200748741) 甚至打不过我的线段树+树剖更不用说树状数组了。
什么？你问我为什么不能写进一个全局平衡二叉树里？我没见过代码，自己不会分讨子树乱七八糟的永久化标记，所以就没这么干。oi-wiki 上说可以，有没有神犇来试一试？
为啥全局平衡二叉树没有【模板】题？
## code
很多封装。不封装变量和函数的命名会让人疯掉。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
struct edge{
int v,nxt;
}ed[maxn<<1];
int head[maxn],edcnt;
void adde(int u,int v){
ed[++edcnt].nxt=head[u];
ed[edcnt].v=v;
head[u]=edcnt;
}
ll mod;
ll add(ll x,ll y){
ll res=x+y;
if(res>=mod) res-=mod;
if(res<=-mod) res+=mod;
if(res<=mod||res>=mod) return res%mod;
return res;
}
ll mul(ll x,ll y){return (x*y)%mod;}
template<typename T>
void addto(T &x,T y){x=add(x,y);}
int root;
int dep[maxn],sz[maxn],fa[maxn];
int dfn[maxn],redfn[maxn],dfncnt;
struct GBST{
struct node{
int l,r,mid;
int ls,rs,fa,rt;
int sz;
ll add_lazy,sumv;
void clear(){memset(this,0,sizeof(node));}
}tr[maxn<<1];
int idx;
int newnode(int l,int r,int mid){
int p=++idx;tr[p].clear();
tr[p].l=l;tr[p].r=r;tr[p].mid=mid;
return p;
}
int wson[maxn],top[maxn];
void dfs1(int u,int f,int d){
sz[u]=1;fa[u]=f;dep[u]=d;wson[u]=0;
++dfncnt;dfn[dfncnt]=u;redfn[u]=dfncnt;
for(int i=head[u];i;i=ed[i].nxt){
int v=ed[i].v;if(v==f) continue;
dfs1(v,u,d+1);sz[u]+=sz[v];
if(!wson[u]||sz[wson[u]]<sz[v]) wson[u]=v;
}
}
void pushup(int p){
tr[p].sumv=add(mul(tr[p].sz,tr[p].add_lazy),
add(tr[tr[p].ls].sumv,tr[tr[p].rs].sumv));
}
int b[maxn],pbs[maxn],bcnt;
int build(int l,int r,int rt){
if(r<l) return 0;
if(l==r){
int mid=l,p=b[mid];if(!rt) rt=p;
tr[p].clear();tr[p].l=l;tr[p].r=r;tr[p].mid=mid;
tr[p].rt=rt;tr[p].sz=1;tr[p].sumv=0;
return p;
}int mid=lower_bound(pbs+l,pbs+r+1,(pbs[l-1]+pbs[r]+1)/2)-pbs;
if(mid==r) mid--;int p=newnode(l,r,mid);if(!rt) rt=p;
int ls=build(l,mid,rt),rs=build(mid+1,r,rt);
tr[p].ls=ls,tr[p].rs=rs;tr[p].rt=rt;
tr[p].sz=tr[tr[p].ls].sz+tr[tr[p].rs].sz;
if(ls) tr[ls].fa=p;if(rs) tr[rs].fa=p;
pushup(p);return p;
}
int dfs2(int u){
for(int p=u;p;p=wson[p]) for(int i=head[p];i;i=ed[i].nxt){
int v=ed[i].v;if(v==fa[p]||v==wson[p]) continue;
tr[dfs2(v)].fa=p;///not u!!!
}bcnt=0;
for(int p=u;p;p=wson[p]){
b[++bcnt]=p;top[p]=u;
pbs[bcnt]=pbs[bcnt-1]+sz[p]-sz[wson[p]];//no +1
}return build(1,bcnt,0);
}
void addf(int p,ll v){
addto(tr[p].add_lazy,v);
addto(tr[p].sumv,mul(tr[p].sz,v));
}
void chg_tree(int p,int l,int r,ll v){
if(!p||r<l) return ;
if(l<=tr[p].l&&tr[p].r<=r) return addf(p,v);
if(l<=tr[p].mid) chg_tree(tr[p].ls,l,r,v);
if(tr[p].mid<r) chg_tree(tr[p].rs,l,r,v);pushup(p);
}
ll get_lns(int p,int l,int r){
int L=max(l,tr[p].l),R=min(r,tr[p].r);
return max(0,R-L+1);
}
ll query_tree(int p,int l,int r){
if(!p||r<l) return 0;
if(l<=tr[p].l&&tr[p].r<=r) return tr[p].sumv;
ll res=mul(tr[p].add_lazy,get_lns(p,l,r));
if(r<=tr[p].mid) return add(query_tree(tr[p].ls,l,r),res);
if(tr[p].mid<l) return add(query_tree(tr[p].rs,l,r),res);
return add(res,add(query_tree(tr[p].ls,l,r),query_tree(tr[p].rs,l,r)));
}
int get_lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}return dep[x]<dep[y]?x:y;
}
struct line{int p,l,r;};vector<line> lns;
void split(int x,int y){
lns.clear();
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
lns.push_back({tr[x].rt,1,tr[x].mid});
x=tr[tr[x].rt].fa;
}if(dep[x]>dep[y]) swap(x,y);
lns.push_back({tr[x].rt,tr[x].mid,tr[y].mid});
}
void chg(ll v){for(line x:lns) chg_tree(x.p,x.l,x.r,v);}
ll query(){
ll res=0;
for(line x:lns) addto(res,query_tree(x.p,x.l,x.r));
return res;
}
void prepare(){
dfncnt=0;dfs1(root,0,1);idx=sz[root];dfs2(root);
}
};GBST tr_LL;
struct BIT{
int n;ll a[maxn],ai[maxn];
void prepare(int n_){n=n_;for(int i=1;i<=n;i++) ai[i]=a[i]=0;}
void adda(int p,ll v){for(;p<=n;p+=p&-p) addto(a[p],v);}
void addai(int p,ll v){for(;p<=n;p+=p&-p) addto(ai[p],v);}
void chg(int l,int r,ll v){
adda(l,v);adda(r+1,-v);
addai(l,mul(l-1,v));addai(r+1,-mul(r,v));
}
ll querya(int p){ll s=0;for(;p;p-=p&-p) addto(s,a[p]);return s;}
ll queryai(int p){ll s=0;for(;p;p-=p&-p) addto(s,ai[p]);return s;}
ll query(int p){return add(mul(p,querya(p)),-queryai(p));}
ll query(int l,int r){return add(query(r),-query(l-1));}
};BIT tr_SS;
struct BIT2{
int n;ll a[maxn];
void prepare(int n_){n=n_;for(int i=1;i<=n;i++) a[i]=0;}
void chg(int p,ll v){for(;p<=n;p+=p&-p) addto(a[p],v);}
ll query(int p){ll s=0;for(;p;p-=p&-p) addto(s,a[p]);return s;}
ll query(int l,int r){return add(query(r),-query(l-1));}
};BIT2 tr_LS,tr_LSi;
struct DFOT{
BIT2 tr;
void prepare(int n_){tr.prepare(n_);}
void chg(int p,ll v){
tr.chg(redfn[p],v);tr.chg(redfn[p]+sz[p],-v);
}
ll query(int p){return tr.query(redfn[p]);}
};DFOT tr_SL,tr_SLi;
void path_add(int x,int y,ll v){
tr_LL.split(x,y);tr_LL.chg(v);
int lca=tr_LL.get_lca(x,y);
auto up_add=[](int p,ll val){
if(!p) return ;
tr_LS.chg(redfn[p],val);tr_LSi.chg(redfn[p],mul(dep[p]+1,val));
};up_add(x,v);up_add(y,v);up_add(lca,-v);up_add(fa[lca],-v);
}
void sub_add(int x,ll v){
tr_SS.chg(redfn[x],redfn[x]+sz[x]-1,v);
tr_SL.chg(x,v);tr_SLi.chg(x,mul(dep[x]-1,v));
}
ll path_query(int x,int y){
tr_LL.split(x,y);ll res=tr_LL.query();
int lca=tr_LL.get_lca(x,y);
auto up_query=[&](int p,ll v){
if(!p) return ;
addto(res,v*add(mul(dep[p],tr_SL.query(p)),-tr_SLi.query(p)));
};up_query(x,1);up_query(y,1);up_query(lca,-1);up_query(fa[lca],-1);
return (res%mod+mod)%mod;
}
ll sub_query(int x){
ll res=tr_SS.query(redfn[x],redfn[x]+sz[x]-1);
addto(res,tr_LSi.query(redfn[x],redfn[x]+sz[x]-1));
addto(res,-mul(tr_LS.query(redfn[x],redfn[x]+sz[x]-1),dep[x]));
return (res%mod+mod)%mod;
}
int n,m;
ll a[maxn];
int main(){
scanf("%d%d%d%lld",&n,&m,&root,&mod);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1,u,v;i<=n-1;i++) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
tr_LL.prepare(),tr_SL.prepare(n),tr_SLi.prepare(n);
tr_LS.prepare(n),tr_LSi.prepare(n),tr_SS.prepare(n);
for(int i=1;i<=n;i++) path_add(i,i,a[i]);
for(int i=1;i<=m;i++){
int op;scanf("%d",&op);
if(op==1){
int x,y;ll v;scanf("%d%d%lld",&x,&y,&v);
path_add(x,y,v);
}else if(op==2){
int x,y;scanf("%d%d",&x,&y);
printf("%lld\n",path_query(x,y));
}else if(op==3){
int x;ll v;scanf("%d%lld",&x,&v);
sub_add(x,v);
}else if(op==4){
int x;scanf("%d",&x);
printf("%lld\n",sub_query(x));
}
}
return 0;
}
```