题解 P3833 【[SHOI2012]魔法树】
如果你还不会树链剖分，可以先尝试这道模板题：【模板】轻重链剖分
这道题可以说是树链剖分套线段树的模板题，蒟蒻的我花了一下午时间来练树链剖分后终于好像搞懂了呢！虽然看到其他题解有用LCT做，但是蒟蒻的我表示我并不会。
首先介绍一下树链剖分：
根据树的概念，树上存在着许多的链，如本图中，就含有很多的链，例如3-2-1-9-10-11就是其中一条链。
对于一棵树，如果我们已经找出了一条链的情况下，它在链上的操作是线性的。此外，一条链周围点，也可以通过这条链实现快速的维护。
例如，还是上图中的3-2-1-9-10-11这一条链，当我们找出它时，便可以快速的维护4这个点（指4向上一步就可以进入链中，复杂度几乎属于常数），减少了树型结构的复杂度。
综上可知，链在树型结构中的地位非常重要，一颗树可以根据不同剖分成多条链，从而将树型结构优化成接近线性结构，进而运用数据结构维护。
树链剖分分为：重链剖分、长链剖分、实链剖分，一般说树链剖分指的是重链剖分。
我们给出一些定义，并按以下规则划分一颗树：
定义：
重子节点——表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。
轻子节点——表示剩余的所有子结点。
从这个结点到重子节点的边为重边。
到其他轻子节点的边为轻边。
若干条首尾衔接的重边构成重链。
把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。
如图所示，当前一颗树已经被按上述要求分成了若干条链。
代码实现：两次dfs
第一次dfs：
fa：记录父节点
dep：记录当前深度
size：记录子树规模
son：当前重儿子是谁,这里主要处理出了每个节点的子树规模以及找出了重儿子，为接下来剖分做准备
void dfs1(int x,int Fa)
{
fa[x]=Fa;
size[x]=1;
dep[x]=dep[Fa]+1;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x])
{
dfs1(to[i]);
size[x]+=size[to[i]];
if(size[son[x]]<size[to[i]])son[x]=to[i];
}
}第二次dfs：
top：当前每个点所在链的顶端节点
seg、rev：对每一个节点按 按链的顺序重新编号，这样同一链上的点编号相邻
这里找出了每个点对应的链的顶点，以此划分链
void dfs2(int x)
{
if(son[fa[x]]!=x)top[x]=x;
else top[x]=top[fa[x]];
seg[x]=++dfn;
rev[dfn]=x;
if(son[x])dfs2(son[x]);
for(rg i=head[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
dfs2(to[i]);
}重链剖分的性质:
树上每个节点都属于且仅属于一条重链 。
所有的重链将整棵树 完全剖分 。
在剖分时优先遍历重儿子，最后重链的 DFS 序就会是连续的。
一颗子树内的 DFN 序是连续的。
可以发现，当我们向下经过一条 轻边 时，所在子树的大小至少会除以二因此每过一条链复杂度至少除以二，最终复杂度为logn级别。
因此，对于树上的任意一条路径，把它拆分成从lca分别向两边往下走，分别最多走logn次，因此，树上的每条路径都可以被拆分成不超过logn条重链。
<此处介绍大多引用xj学长的细心讲解啦~~~>
然后我们就可以干很多事情，例如
套线段树！！
因此我们就可以把线段树的板子打上去了！！
这道题就用线段树维护区间和以及区间最大值，但因为树链剖分后每次change_son修改的的区间是从seg[ x ]到seg[ x ]+size[ x ]-1（相当于seg记录的是dfs序啦）
（并且这道题要记得开long long呦）
Code:
< 提供自认为比较清新的码风 >
#define Flowery
#define maxn 400000
#define ll long long
#define rg register long long
#include<bits/stdc++.h>
using namespace std;
int T,n;
struct node
{
ll l,r,val,maxx,lazy;
}gy[maxn];
int to[maxn],head[maxn],nxt[maxn],cnt;
inline void add(ll x,ll y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int fa[maxn],dep[maxn],size[maxn],son[maxn];
void dfs1(ll x)
{
size[x]=1;
dep[x]=dep[fa[x]]+1;
for(rg i=head[x];i;i=nxt[i])
if(to[i]!=fa[x])
{
dfs1(to[i]);
size[x]+=size[to[i]];
if(size[son[x]]<size[to[i]])son[x]=to[i];
}
}
int top[maxn],seg[maxn],rev[maxn],dfn;
void dfs2(ll x)
{
if(son[fa[x]]!=x)top[x]=x;
else top[x]=top[fa[x]];
seg[x]=++dfn;
rev[dfn]=x;
if(son[x])dfs2(son[x]);
for(rg i=head[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])dfs2(to[i]);
}
void push_up(ll x)
{
gy[x].val=gy[2*x].val+gy[2*x+1].val;
}
void push_down(ll x)
{
if(gy[x].lazy)
{
gy[2*x].lazy+=gy[x].lazy;
gy[2*x+1].lazy+=gy[x].lazy;
gy[2*x].val+=(gy[2*x].r-gy[2*x].l+1)*gy[x].lazy;
gy[2*x+1].val+=(gy[2*x+1].r-gy[2*x+1].l+1)*gy[x].lazy;
gy[x].lazy=0;
}
}
void build(ll x,ll l,ll r)
{
gy[x].l=l;gy[x].r=r;
if(l==r)return;
ll mid=(l+r)>>1;
build(2*x,l,mid);
build(2*x+1,mid+1,r);
push_up(x);
}
void modify(ll x,ll l,ll r,ll v)
{
if(gy[x].l>r||gy[x].r<l)return;
if(l<=gy[x].l&&gy[x].r<=r)
{
gy[x].lazy+=v;
gy[x].val+=(gy[x].r-gy[x].l+1)*v;
return;
}
push_down(x);
modify(2*x,l,r,v);
modify(2*x+1,l,r,v);
push_up(x);
}
ll query(ll x,ll l,ll r)
{
if(gy[x].l>r||gy[x].r<l)return 0;
if(l<=gy[x].l&&gy[x].r<=r)return gy[x].val;
push_down(x);
return query(2*x,l,r)+query(2*x+1,l,r);
}
void change(ll u,ll v,ll val)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])swap(u,v);
modify(1,seg[top[u]],seg[u],val);
u=fa[top[u]];
}
if(dep[u]<dep[v])swap(u,v);
modify(1,seg[v],seg[u],val);
}
ll u,v,d;
char opt[2];
int main()
{
scanf("%lld",&n);fa[1]=-1;
for(rg i=1;i<n;i++)
{
scanf("%lld%lld",&u,&v);u++;v++;
add(u,v);add(v,u);
fa[v]=u;
}
dep[1]=1;dfs1(1);dfs2(1);build(1,1,n);
scanf("%lld",&T);
while(T--)
{
scanf("%s",opt);
if(opt[0]=='A')
{
scanf("%lld%lld%lld",&u,&v,&d);u++;v++;
change(u,v,d);
}
if(opt[0]=='Q')
{
scanf("%lld",&u);u++;
printf("%lld\n",query(1,seg[u],seg[u]+size[u]-1));
}
}
return 0;
}(11-3 modify:图片不小心崩啦)
my blog