记录编号	160615	评测结果	AAAAAAAAAA
题目名称	1963.[HAOI 2015]树上操作	最终得分	100
用户昵称	TAT	是否通过	通过
代码语言	C++	运行时间	0.551 s
提交时间	2015-04-29 06:43:31	内存使用	12.31 MiB

#include<stdio.h>
typedef long long lnt;
const int maxn=100010;
char ch[5000000],*ptr=ch;
lnt c[maxn],c1[maxn],c2[maxn];
int cnt,w[maxn],en[maxn],val[maxn];
int n,tot,head[maxn],to[maxn<<1],next[maxn<<1];
int fa[maxn],siz[maxn],top[maxn],son[maxn],dep[maxn];
void ins(int u,int v){
	to[++tot]=v,next[tot]=head[u],head[u]=tot;
}
void add1(int i,int x){
	while(i<=n) c1[i]+=x,i+=i&-i;
}
void add2(int i,lnt x){
	while(i<=n) c2[i]+=x,i+=i&-i;
}
lnt ask1(int i){
	static lnt res;
	for(res=0;i>0;i-=i&-i) res+=c1[i];
	return res;
}
lnt ask2(int i){
	static lnt res;
	for(res=0;i>0;i-=i&-i) res+=c2[i];
	return res;
}
void in(int &x){
	static bool gg;
	while(*ptr<40) ptr++;
	if(*ptr!=45) x=*ptr-48,gg=0;
	else x=0,gg=1;ptr++;
	while(*ptr>47) x=x*10+*ptr++-48;
	if(gg) x=-x;
}
void dfs1(int x){
	siz[x]=1;
	for(int i=head[x];i;i=next[i])
		if(to[i]!=fa[x]){
			dep[to[i]]=dep[x]+1;
			fa[to[i]]=x;
			dfs1(to[i]);
			siz[x]+=siz[to[i]];
			if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
		}
}
void dfs2(int x,int tp){
	top[x]=tp,w[x]=++cnt,c[cnt]=val[x]+c[cnt-1];
	if(son[x]) dfs2(son[x],tp);
	for(int i=head[x];i;i=next[i])
		if(to[i]!=fa[x]&&to[i]!=son[x])
			dfs2(to[i],to[i]);
	en[x]=cnt;
}
int main(){
	freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
	fread(ch,1,5000000,stdin);
	long long ans;
	int m,i,u,v,op;
	in(n),in(m);
	for(i=1;i<=n;i++) in(val[i]);
	for(i=1;i<n;i++) in(u),in(v),ins(u,v),ins(v,u);
	dfs1(1),dfs2(1,1);
	while(m--){
		in(op);
		switch(op){
			case 1:in(u),in(v),add1(w[u],v),add2(w[u],(lnt)w[u]*v),add1(w[u]+1,-v),add2(w[u]+1,-(lnt)v*(w[u]+1));break;
			case 2:in(u),in(v),add1(w[u],v),add2(w[u],(lnt)w[u]*v),add1(en[u]+1,-v),add2(en[u]+1,-(lnt)v*(en[u]+1));break;
			case 3:
				ans=0,in(u);
				for(int fu=top[u];fu!=1;u=fa[fu],fu=top[u])
					ans+=c[w[u]]-c[w[fu]-1]+ask1(w[u])*(w[u]+1)-ask2(w[u])-ask1(w[fu]-1)*w[fu]+ask2(w[fu]-1);
				printf("%lld\n",ans+c[w[u]]+ask1(w[u])*(w[u]+1)-ask2(w[u]));break;
		}
	}
	return 0;
}