dfs序，树链剖分
#include#include using namespace std;#define N 100001typedef long long LL;int n,a[N];int front[N],nxt[N<<1],to[N<<1],tot;int fa[N],siz[N],dep[N];int bl[N];int id,L[N],R[N];int dy[N];LL sum[N<<2],tag[N<<2];LL ans;void read(int &x){ x=0; int f=1; char c=getchar(); while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } x*=f;}void add(int u,int v){ to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;}void dfs1(int x){ siz[x]=1; for(int i=front[x];i;i=nxt[i]) if(to[i]!=fa[x]) { fa[to[i]]=x; dep[to[i]]=dep[x]+1; dfs1(to[i]); siz[x]+=siz[to[i]]; }}void dfs2(int x,int top){ bl[x]=top; L[x]=++id; dy[id]=x; int y=0; for(int i=front[x];i;i=nxt[i]) if(to[i]!=fa[x] && siz[to[i]]>siz[y]) y=to[i]; if(!y) { R[x]=id; return; } else dfs2(y,top); for(int i=front[x];i;i=nxt[i]) if(to[i]!=fa[x] && to[i]!=y) dfs2(to[i],to[i]); R[x]=id;}void build(int k,int l,int r){ if(l==r) { sum[k]=a[dy[l]]; return; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); sum[k]=sum[k<<1]+sum[k<<1|1];}void down(int k,int l,int r){ int mid=l+r>>1; sum[k<<1]+=tag[k]*(mid-l+1); sum[k<<1|1]+=tag[k]*(r-mid); tag[k<<1]+=tag[k]; tag[k<<1|1]+=tag[k]; tag[k]=0;} void add(int k,int l,int r,int opl,int opr,int x){ if(l>=opl && r<=opr) { sum[k]+=1LL*(r-l+1)*x; tag[k]+=x; return; } if(tag[k]) down(k,l,r); int mid=l+r>>1; if(opl<=mid) add(k<<1,l,mid,opl,opr,x); if(opr>mid) add(k<<1|1,mid+1,r,opl,opr,x); sum[k]=sum[k<<1]+sum[k<<1|1];}void query(int k,int l,int r,int opl,int opr){ if(l>=opl && r<=opr) { ans+=sum[k]; return; } if(tag[k]) down(k,l,r); int mid=l+r>>1; if(opl<=mid) query(k<<1,l,mid,opl,opr); if(opr>mid) query(k<<1|1,mid+1,r,opl,opr);}void QUERY(int x){ ans=0; while(x) { query(1,1,n,L[bl[x]],L[x]); x=fa[bl[x]]; } cout< <<'\n';} int main(){ int m; read(n); read(m); for(int i=1;i<=n;++i) read(a[i]); int u,v; for(int i=1;i
4034: [HAOI2015]树上操作
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 6461 Solved: 2148[][][]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
Sample Output
6 9 13
HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。