树链剖分/dfs序
树上单点修改+子树修改+链查询
其实用dfs序做也可以……
其实树链剖分就是一个特殊的dfs序嘛= =所以树链剖分也可以搞子树～（Orz ZYF）
至于为什么……你看在做剖分的时候不也是dfs下去的？然后只不过是先走重儿子，但本质上也是一个dfs序，所以dfs序能搞的子树操作，链剖也是兹瓷的～
然后随便水水就过了……
WA了一发：查询从x到1的权值和的时候，写成了while(top[x])，改成while(x)后就过了……
/**************************************************************
Problem: 4034
User: Tunix
Language: C++
Result: Accepted
Time:2192 ms
Memory:27956 kb
****************************************************************/ //BZOJ 4034
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=2e5+,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/ int to[N<<],nxt[N<<],head[N],cnt;
void add(int x,int y){
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
LL n,m,a[N];
LL sm[N<<],ad[N<<];
#define mid (l+r>>1)
#define L (o<<1)
#define R (o<<1|1)
inline void maintain(int o,int l,int r){
sm[o]=sm[L]+sm[R];
}
inline void Push_down(int o,int l,int r){
if (ad[o]) {
ad[L]+=ad[o]; sm[L]+=ad[o]*(mid-l+);
ad[R]+=ad[o]; sm[R]+=ad[o]*(r-mid);
ad[o]=;
}
}
void update(int o,int l,int r,int ql,int qr,LL v){
if (ql<=l && qr>=r) sm[o]+=v*(LL)(r-l+),ad[o]+=v;
else{
Push_down(o,l,r);
if (ql<=mid) update(L,l,mid,ql,qr,v);
if (qr>mid) update(R,mid+,r,ql,qr,v);
maintain(o,l,r);
}
}
LL query_it(int o,int l,int r,int ql,int qr){
if (ql<=l && qr>=r) return sm[o];
else{
LL ans=; Push_down(o,l,r);
if (ql<=mid) ans+=query_it(L,l,mid,ql,qr);
if (qr>mid) ans+=query_it(R,mid+,r,ql,qr);
return ans;
}
} int top[N],fa[N],dep[N],tid[N],st[N],ed[N],son[N],size[N];
void dfs(int x){
size[x]=; son[x]=;
int mx=;
for(int i=head[x];i;i=nxt[i])
if (to[i]!=fa[x]){
fa[to[i]]=x;
dep[to[i]]=dep[x]+;
dfs(to[i]);
size[x]+=size[to[i]];
if (size[to[i]]>mx) mx=size[to[i]],son[x]=to[i];
}
}
int tot;
bool vis[N];
void connect(int x,int f){
vis[x]=;
top[x]=f;
st[x]=tid[x]=++tot;
if (son[x]) connect(son[x],f);
for(int i=head[x];i;i=nxt[i])
if (!vis[to[i]])
connect(to[i],to[i]);
ed[x]=tot;
}
LL query(int x){
LL ans=;
while(x){
ans+=query_it(,,n,tid[top[x]],tid[x]);
x=fa[top[x]];
}
return ans;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("4034.in","r",stdin);
freopen("4034.out","w",stdout);
#endif
n=getint(); m=getint();
F(i,,n) a[i]=getint();
F(i,,n){
int x=getint(),y=getint();
add(x,y);
}
dfs();
connect(,);
F(i,,n) update(,,n,tid[i],tid[i],a[i]);
int cmd,x,y;
F(i,,m){
cmd=getint(); x=getint();
if (cmd==){
y=getint();
update(,,n,tid[x],tid[x],y);
}else if (cmd==){
y=getint();
update(,,n,st[x],ed[x],y);
}else{
printf("%lld\n",query(x));
}
}
return ;
}
4034: [HAOI2015]T2
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 265 Solved: 113
[Submit][Status][Discuss]
Description
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
Input
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操
作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
Output
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
Sample Input
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
Sample Output
6
9
13
9
13
HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不
会超过 10^6 。