记录编号 |
413535 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[HAOI 2015]树上操作 |
最终得分 |
100 |
用户昵称 |
Hzoi_Maple |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.862 s |
提交时间 |
2017-06-11 18:28:08 |
内存使用 |
13.67 MiB |
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
int n,m,x,y,z,w[200001];
int adj[200001],num;
ll add[400001],zh[400001];
struct kk
{
int s,t,next;
}k[200001];
void swap(ll &a,ll &b){
ll c=a;
a=b;
b=c;
}
inline int read(){
int zh=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
zh=zh*10+ch-'0';
ch=getchar();
}
return zh*f;
}
inline void pushup(int i)
{
zh[i]=zh[i<<1]+zh[i<<1|1];
}
void init(int x,int y){
k[num].s=x;
k[num].t=y;
k[num].next=adj[x];
adj[x]=num++;
}
int fa[100001],dp[100001],son[100001],size[100001];
void Dfs1(int x,int father,int dep){
fa[x]=father;dp[x]=dep;
size[x]=1;son[x]=0;
for(int i=adj[x];i!=-1;i=k[i].next){
int o=k[i].t;
if(o!=father){
Dfs1(o,x,dep+1);
size[x]+=size[o];
if(size[son[x]]<size[o])
son[x]=o;
}
}
}
int top[100001],id[100001],cnt,pos[100001];
int wcx[100001],yl[100001];//记得某皮说过:只可意会不可言传~
void Dfs2(int u,int tp){
top[u]=tp;id[u]=++cnt;
pos[cnt]=u;wcx[u]=cnt;
if(son[u])
Dfs2(son[u],tp);
for(int i=adj[u];i!=-1;i=k[i].next){
int o=k[i].t;
if(o!=fa[u]&&o!=son[u]){
Dfs2(o,o);
}
}
yl[u]=cnt;
}
void build(int l,int r,int x){
add[x]=0;
if(l==r){
zh[x]=w[pos[l]];
return;
}
int mid=(l+r)>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
zh[x]=zh[x<<1]+zh[x<<1|1];
}
void pushd(int x,int len){
if(add[x]){
add[x<<1]+=add[x];
add[x<<1|1]+=add[x];
zh[x<<1]+=add[x]*(len-(len>>1));
zh[x<<1|1]+=add[x]*(len>>1);
add[x]=0;
}
}
void update(int L,int R,ll c,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
add[rt]+=c;
zh[rt]+=(ll)c*(r-l+1);
return;
}
pushd(rt,r-l+1);
int mid=(l+r)>>1;
if(L<=mid)
update(L,R,c,l,mid,2*rt);
if(mid<R)
update(L,R,c,mid+1,r,2*rt+1);
pushup(rt);
}
ll ask(int s,int t,int l,int r,int x){
if(s<=l&&t>=r) return zh[x];
pushd(x,r-l+1);
int mid=(l+r)>>1;ll ans=0;
if(s<=mid) ans+=ask(s,t,l,mid,2*x);
if(t>mid) ans+=ask(s,t,mid+1,r,2*x+1);
return ans;
}
ll query(int x,int y){
int fx=top[x],fy=top[y];
ll res=0;
while(fx^fy){
if(dp[fx]<dp[fy]){
swap(x,y);
swap(fx,fy);
}
res+=ask(id[fx],id[x],1,n,1);
x=fa[fx];fx=top[x];
}
if(dp[x]>dp[y]) swap(x,y);
res+=ask(id[x],id[y],1,n,1);
return res;
}
int main()
{
freopen("haoi2015_t2.in","r",stdin);
freopen("haoi2015_t2.out","w",stdout);
memset(adj,-1,sizeof(adj));
n=read();m=read();
for(int i=1;i<=n;++i)
w[i]=read();
for(int i=1;i<n;++i){
x=read();y=read();
init(x,y);
init(y,x);
}
Dfs1(1,0,0);
Dfs2(1,1);
build(1,n,1);
for(int i=1;i<=m;++i){
x=read();
if(x==1){
y=read();z=read();
update(wcx[y],wcx[y],z,1,n,1);
}
if(x==2){
y=read();z=read();
update(wcx[y],yl[y],z,1,n,1);
}
if(x==3){
y=read();
printf("%lld\n",query(1,y));
}
}
// while(1);
return 0;
}