题解 P3384 【【模板】树链剖分】
teafrogsf
2017-10-11 21:22:04
本题是树链剖分的裸题。虽然大家都知道，树状数组的常数比较小，但由于太难写了，于是大部分人也都是写的线段树。
我的代码163行，而这个行数是**纯天然缩行**形成的，也就是说通过人工压缩可以压到150行以内。
而且这个代码实际上还是长了。为什么呢？因为我用了许多if来取模。
不开long long的原因是在Linux下long long会变得特别慢，而线段树常数也比较大。
而如果有时候不分青红皂白直接取模就会导致有时候会变得比较慢，某些题目会故意这样来卡常数。
此外注意**等于**mod数也要取模。
实测比我的同学快300ms。
主要是讲述以上的优化思路，代码仅供参考，每个人的代码风格都不一样，重要的是细心。
```cpp
#include<cstdio>
#include<iostream>
#define neko 100010
#define meko 100010
#define mid ((l+r)>>1)
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define ori tagl,tagr
#define f(i,a,b) for(register int i=a;i<=b;++i)
using std::swap;
int Sum[neko<<2],Add[neko<<2];
typedef int arr[neko];
int n,m,root,mod,t,cnt;
arr siz,fa,son,top,dep,w,head,ord,a;
//first dfs: siz fa son dep
//second dfs: top
struct node
{
int u,v,next;
}e[meko<<1];
void read(int &x)
{
char c=getchar();int p=1;x=0;
while(!isdigit(c)){c=getchar();if(c=='-')p=-1;}
while(isdigit(c))
{
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}x*=p;
}
void add(int x,int y)
{
e[++t].u=x;
e[t].v=y;
e[t].next=head[x];
head[x]=t;
}
void dfs(int u)//其实这是树剖最容易打的地方
{
dep[u]=dep[fa[u]]+1;
siz[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v!=fa[u])
{
fa[v]=u;
dfs(v);
siz[u]+=siz[v];
if(son[u]==-1||siz[v]>siz[son[u]])son[u]=v;
}
}
}
void dfs2(int u)
{
w[u]=++cnt;
ord[cnt]=u;
if(u==son[fa[u]])top[u]=top[fa[u]];
else top[u]=u;
if(son[u]!=-1)dfs2(son[u]);
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v!=fa[u]&&v!=son[u])dfs2(v);
}
}
void pushup(int root)
{
Sum[root]=Sum[root<<1]+Sum[root<<1|1];
if(Sum[root]>=mod)Sum[root]%=mod;
}
void build(int root,int l,int r)
{
if(l==r)Sum[root]=a[ord[l]];
else
{
build(lson);
build(rson);
pushup(root);
}
}
void pushdown(int root,int l,int r)
{
if(Add[root])
{
Add[root<<1]+=Add[root];
Add[root<<1|1]+=Add[root];
if(Add[root<<1]>=mod)Add[root<<1]%=mod;
if(Add[root<<1|1]>=mod)Add[root<<1|1]%=mod;
Sum[root<<1]+=(mid-l+1)*Add[root];
Sum[root<<1|1]+=(r-mid)*Add[root];
if(Sum[root<<1]>=mod)Sum[root<<1]%=mod;
if(Sum[root<<1|1]>=mod)Sum[root<<1|1]%=mod;
Add[root]=0;
}
}
void update(int root,int l,int r,int tagl,int tagr,int x)
{
if(l>=tagl&&r<=tagr)
{
Add[root]+=x;
Sum[root]+=(r-l+1)*x;
if(Sum[root]>=mod)Sum[root]%=mod;
}
else
{
pushdown(root,l,r);
if(tagl<=mid)update(lson,ori,x);
if(tagr>mid)update(rson,ori,x);
pushup(root);
}
}
int query(int root,int l,int r,int tagl,int tagr)
{
if(l>=tagl&&r<=tagr)return Sum[root];
else
{
pushdown(root,l,r);
int tmp=0;
if(tagl<=mid)tmp+=query(lson,ori);
if(tmp>=mod)tmp%=mod;
if(tagr>mid)tmp+=query(rson,ori);
return tmp>=mod?tmp%mod:tmp;
}
}
void pathu(int l,int r,int x)
{
while(top[l]!=top[r])
{
if(dep[top[l]]<dep[top[r]])swap(l,r);
update(1,1,n,w[top[l]],w[l],x);
l=fa[top[l]];
}if(dep[l]>dep[r])swap(l,r);
update(1,1,n,w[l],w[r],x);
}
int pathq(int l,int r)
{
int sum=0;
while(top[l]!=top[r])
{
if(dep[top[l]]<dep[top[r]])swap(l,r);
sum+=query(1,1,n,w[top[l]],w[l]);if(sum>=mod)sum%=mod;
l=fa[top[l]];
}if(dep[l]>dep[r])swap(l,r);
return (sum+query(1,1,n,w[l],w[r]))%mod;
}
int main()
{
int _,_2,_3,_4,x,y;
read(n),read(m),read(root),read(mod);
f(i,1,n)read(a[i]),son[i]=-1;
f(i,1,n-1)read(x),read(y),add(x,y),add(y,x);
dfs(root);
dfs2(root);
build(1,1,n);
f(i,1,m)
{
read(_),read(_2);
if(_==1)read(_3),read(_4),pathu(_2,_3,_4);
if(_==2)read(_3),printf("%d\n",pathq(_2,_3));
if(_==3)read(_3),update(1,1,n,w[_2],w[_2]+siz[_2]-1,_3);
if(_==4)printf("%d\n",query(1,1,n,w[_2],w[_2]+siz[_2]-1));
}return 0;
}
```