放错代码了/jk
```cpp
// Problem: P3178 [HAOI2015]树上操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3178
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define M 100005
#define ll (i*2)
#define rr (i*2+1)
int n,m,r,p=200000000000000,U,V,opt,x,y,z,cntp;
int a[M],w[M],d[M],top[M],id[M],fid[M],siz[M],fa[M],son[M];
/*id[i]=j,意为原节点i的id为j,fid则相反*/
vector<int>roadu[M],road[M];
struct node
{
int s,fl,fr,laz;
}t[M*9];
void push_down(int i)
{
if(!t[i].laz) return;
int k=t[i].laz;
t[ll].s+=(t[ll].fr-t[ll].fl+1)*k;
t[rr].s+=(t[rr].fr-t[rr].fl+1)*k;
t[ll].laz+=k;t[rr].laz+=k;
t[ll].s%=p;t[rr].s%=p;
t[i].laz=0;
}
void build(int l,int r,int i)
{
t[i].fl=l;t[i].fr=r;t[i].laz=0;
if(l==r)
{
t[i].s=w[l];
if(t[i].s>p){t[i].s%=p;}
return;
}
int mid=(l+r)/2;
build(l,mid,ll);
build(mid+1,r,rr);
t[i].s=t[ll].s+t[rr].s;t[i].s%=p;
}
void plused(int l,int r,int x,int y,int i,int k)/*在区间i[x-y]操作,把[l-r]加上k*/
{
// cout<<x<<' '<<y<<endl;
if(x>=l&&y<=r)/*l--x--y--r*/
{
t[i].laz+=k;
t[i].s+=(y-x+1)*k;
return;
}
push_down(i);
int mid=(x+y)/2;
if(mid>=l)/*[x-mid]是否交[l-r]? */
{
plused(l,r,x,mid,ll,k);
}
if(mid<r)
{
plused(l,r,mid+1,y,rr,k);
}
t[i].s=t[ll].s+t[rr].s;t[i].s%=p;
}
int Query(int l,int r,int x,int y,int i)/*在区间i[x-y]操作,求i与[l-r]的交的和*/
{
int res=0,mid=(x+y)/2;
if(x>=l&&y<=r)/*l-r包含x-y l--x--y--t*/
{
return t[i].s%p;
}
push_down(i);
if(mid>=l)
{
res+=Query(l,r,x,mid,ll);res%=p;
}
if(mid<r)
{
res+=Query(l,r,mid+1,y,rr);res%=p;
}
return res;
}
void dfs1(int x)
{
if(x==r){d[x]=1;}
siz[x]=1;
int sonm=-1;
for(int i=0;i<road[x].size();i++)
{
if(d[road[x][i]]){continue;}
d[road[x][i]]=d[x]+1;
dfs1(road[x][i]);
fa[road[x][i]]=x;
siz[x]+=siz[road[x][i]];
if(siz[road[x][i]]>sonm)
{
sonm=siz[road[x][i]];
son[x]=road[x][i];
}
}
}
void dfs2(int x,int y)
{
cntp++;
w[cntp]=a[x];
id[x]=cntp;
fid[cntp]=x;
top[x]=y;
if(son[x]==0){return;}
dfs2(son[x],y);
for(int i=0;i<road[x].size();i++)
{
if(id[road[x][i]]) continue;
dfs2(road[x][i],road[x][i]);
}
}
void pLCA()
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
// cout<<x<<' '<<top[x]<<' '<<id[x]<<' '<<id[top[x]]<<endl;
plused(id[top[x]],id[x],1,n,1,z);
x=fa[top[x]];
}
if(d[x]<d[y]) swap(x,y);//d[x]=3,dy=2
plused(id[y],id[x],1,n,1,z);
}
void qLCA()/*询问 x,y 两个点的最短路径权值和*/
{
int res=0;
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
res+=Query(id[top[x]],id[x],1,n,1)%p;
res%=p;
// cout<<res<<endl;
x=fa[top[x]];
}
if(d[x]<d[y]) swap(x,y);//d[x]=3,dy=2
res+=Query(id[y],id[x],1,n,1)%p;res%=p;
cout<<res<<endl;
}
void ptree()
{
plused(id[x],id[x]+siz[x]-1,1,n,1,z);
}
signed main()
{
cin>>n>>m;
r=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
cin>>U>>V;
road[U].push_back(V);
road[V].push_back(U);
}
dfs1(r);
dfs2(r,r);
// for(int i=1;i<=n;i++)
// {
// cout<<top[i]<<' '<<id[i]<<' '<<son[i]<<endl;
// }
build(1,n,1);//建xds
for(int i=1;i<=m;i++)
{
cin>>opt;
if(opt==1)
{
cin>>x>>z;y=x;
pLCA();
}
if(opt==2)
{
cin>>x>>z;
ptree();
}
if(opt==3)
{
cin>>x;y=1;
qLCA();
}
}
return 0;
}
```
by 冰糖鸽子 @ 2021-01-20 13:19:54