DFS序（带入栈出栈标记）：
对于一个节点，我们用L[i]和R[i]表示它入栈和出栈的时间。这样[L[i],R[i]]就表示了以i为根的区间。
我们还要将入栈的符号为+，出栈的符号为-，那么令V[i]=sig[i]*val[i]。
这样有什么好处呢？
1.对于一个节点x到根的节点val权值和，等于Sum{V[1,R[x]]}。
2.对于将一个子树所有值+v，等于将[L[i],R[i]]的所有V值+v
这便是一个经典的线段树
但是这样有什么局限性呢？答案必须满足区间加减法（例如这道题DFS序无法求最大值）。
否则怎么做呢？树链剖分！！！！！！！！！！！！！
DFS序好像是Fenwich，树链剖分好像是Splay
-------------------------------------------------------------------------------------------------------
暑假出的题，其实是从一道BZOJ的题摘下来的，原题还有换根操作，只能用splay动态维护DFS序列。
恩先放一个之前写的DFS序列（带入栈出栈标记）+线段树版本的：（写得丑请不要介意）
询问O(logn)修改O(logn)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,first[maxn],next[maxn],v[maxn],e;
void AddEdge(int a,int b)
{
v[++e]=b;
next[e]=first[a];
first[a]=e;
}
int F[maxn],L[maxn],s[maxn],val[maxn],tot;
void dfs(int x)
{
F[x]=++tot; s[tot]=;
for(int i=first[x];i;i=next[i]) dfs(v[i]);
L[x]=++tot; s[tot]=-;
}
typedef long long LL;
LL sumv[maxn*],addv[maxn*],sz[maxn*];
void maintain(int o,int L,int R)
{
sumv[o]=;
if(L<R) sumv[o]=sumv[o<<]+sumv[(o<<)|];
sumv[o]+=addv[o]*sz[o];
}
void build(int o,int L,int R)
{
if(L==R) addv[o]=val[L],sz[o]=s[L];
else
{
int M=L+R>>,lc=o<<,rc=lc|;
build(lc,L,M); build(rc,M+,R);
sz[o]=sz[lc]+sz[rc];
}
maintain(o,L,R);
}
int ql,qr,va;
LL query(int o,int L,int R,int add)
{
if(ql<=L&&R<=qr) return sumv[o]+add*sz[o];
else
{
int M=L+R>>,lc=o<<,rc=lc|;
LL ans=;
if(ql<=M) ans+=query(lc,L,M,add+addv[o]);
if(qr>M) ans+=query(rc,M+,R,add+addv[o]);
return ans;
}
}
void update(int o,int L,int R)
{
if(ql<=L&&R<=qr) addv[o]+=va;
else
{
int M=L+R>>,lc=o<<,rc=lc|;
if(ql<=M) update(lc,L,M);
if(qr>M) update(rc,M+,R);
}
maintain(o,L,R);
}
int main()
{
int p;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&p);
AddEdge(p,i);
}
dfs();
for(int i=;i<=n;i++) scanf("%d",&p),val[L[i]]=val[F[i]]=p;
build(,,n*);
scanf("%d",&m);
char cmd[];
while(m--)
{
scanf("%s",cmd);
if(cmd[]=='Q')
{
scanf("%d",&qr);ql=;qr=F[qr];
printf("%lld\n",query(,,n*,));
}
else
{
scanf("%d%d",&ql,&va);
qr=L[ql]; ql=F[ql];
update(,,n*);
}
}
return ;
}
发现可以用树链剖分做，昨天写了一下，WA掉N发，还是线段树写错了。
询问O(log^2n)修改O(logn)
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
int n,first[maxn],to[maxn],next[maxn],e;
void AddEdge(int u,int v){to[++e]=v;next[e]=first[u];first[u]=e;}//单向边就可以了
int fa[maxn],siz[maxn],son[maxn];
void dfs(int x)//………………
{
siz[x]=;
for(int i=first[x];i;i=next[i])//因为是单向边，下同
{
fa[to[i]]=x;dfs(to[i]);
siz[x]+=siz[to[i]];
if(siz[son[x]]<siz[to[i]]) son[x]=to[i];
}
}
int top[maxn],pos[maxn],mx[maxn],sz;
void build(int x,int tp)//建树时记录DFS序的区间
{
top[x]=tp;pos[x]=++sz;
if(son[x]) build(son[x],tp);
for(int i=first[x];i;i=next[i]) if(to[i]!=son[x]) build(to[i],to[i]);
mx[x]=sz;//右端点
}
int ql,qr;
ll A[maxn],sumv[maxn*],addv[maxn*],val;
ll query(int o,int l,int r,ll add)
{
if(ql<=l&&r<=qr) return sumv[o]+add*(r-l+);
int mid=l+r>>,lc=o<<,rc=lc|;ll ans=;
if(ql<=mid) ans+=query(lc,l,mid,add+addv[o]);
if(qr>mid) ans+=query(rc,mid+,r,add+addv[o]);
return ans;
}
void build(int o,int l,int r)
{
int mid=l+r>>,lc=o<<,rc=lc|;
if(l==r) sumv[o]=addv[o]=A[l];//注意！
else
{
build(lc,l,mid);build(rc,mid+,r);
sumv[o]=sumv[lc]+sumv[rc];
}
}
void update(int o,int l,int r)
{
int mid=l+r>>,lc=o<<,rc=lc|;
if(ql<=l&&r<=qr) addv[o]+=val;
else
{
if(ql<=mid) update(lc,l,mid);
if(qr>mid) update(rc,mid+,r);
}
sumv[o]=;
if(l<r) sumv[o]=sumv[lc]+sumv[rc];////注意叶节点信息，本蒟蒻就在这里WA了N发 TAT
sumv[o]+=(r-l+)*addv[o];
}
void query(int x)
{
ll ans=;
while(top[x]!=)//不停向根节点走
{
ql=pos[top[x]];qr=pos[x];ans+=query(,,n,);
x=fa[top[x]];
}
ql=;qr=pos[x];ans+=query(,,n,);
printf("%lld\n",ans);
}
int main()
{
n=read();
for(int i=;i<=n;i++) AddEdge(read(),i);
dfs();build(,);
for(int i=;i<=n;i++) A[pos[i]]=read();
build(,,n);
int q=read();
while(q--)
{
char tp=getchar();
while(!isalpha(tp)) tp=getchar();
int x=read();
if(tp=='Q') query(x);
else
{
val=read();ql=pos[x];qr=mx[x];
update(,,n);
}
}
return ;
}
其实用DFS序就可以解决了。对于询问时，我们考虑x到根路径上一次对y子树的修改，贡献是(depy-depx+1)*vx，变形后可得depy*sigma(vx)-sigma((depx-1)*vx)，用树状数组分别维护两个值就可以了。初始同理，请读者自行分析。O(logn)
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int n,q,root,first[maxn],next[maxn],to[maxn],e;
void AddEdge(int u,int v) {
to[++e]=v;next[e]=first[u];first[u]=e;
}
int L[maxn],R[maxn],cnt,dep[maxn];
void dfs(int x) {
L[x]=++cnt;
ren dep[to[i]]=dep[x]+,dfs(to[i]);
R[x]=cnt;
}
typedef long long LL;
struct Fenwich {
LL sumv[maxn];
void add(int x,LL v) {for(;x<=n;x+=x&-x) sumv[x]+=v;}
LL sum(int x) {LL ret=;for(;x;x-=x&-x) ret+=sumv[x];return ret;}
}tree1,tree2;
int main() {
n=read();
rep(i,,n) AddEdge(read(),i);
dfs();
rep(x,,n) {
int v=read();
tree2.add(L[x],-v);tree2.add(R[x]+,v);
}
q=read();
while(q--) {
char cmd=getchar();
while(!isalpha(cmd)) cmd=getchar();
if(cmd=='Q') {
int x=read();
printf("%lld\n",tree1.sum(L[x])*dep[x]-tree2.sum(L[x]));
}
else {
int x=read(),v=read();
tree1.add(L[x],v);tree1.add(R[x]+,-v);
tree2.add(L[x],(LL)(dep[x]-)*v);tree2.add(R[x]+,(LL)(-dep[x])*v);
}
}
return ;
}