社区讨论
什么样的码风算好码风?
灌水区参与者 33已保存回复 54
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 54 条
- 当前快照
- 1 份
- 快照标识符
- @mi7y2568
- 此快照首次捕获于
- 2025/11/21 05:29 4 个月前
- 此快照最后确认于
- 2025/11/21 06:57 4 个月前
被老师吐槽不好看懂。。。
CPP#include <cstdio>
#include <algorithm>
#define N 400010
#define LL long long
using namespace std;
LL n,m;
LL val[N],head[N],next[N],vec[N],edge;//存图相关
LL depth[N],f[N],size[N],mson[N];//dfs1相关
LL new_num[N],new_val[N],top[N],cnt;//dfs2相关
long long w[N],tag[N];//线段树相关
void add(LL x,LL y)
{
vec[++edge]=y;
next[edge]=head[x];
head[x]=edge;
}
LL dfs1(LL u,LL fa,LL dep)
{
depth[u]=dep;
f[u]=fa;
size[u]=1;
LL mval=-1;
for(LL i=head[u];i;i=next[i])
{
if(vec[i]==fa) continue;
size[u]+=dfs1(vec[i],u,dep+1);
if(size[vec[i]]>mval) mval=size[vec[i]],mson[u]=vec[i];
}
return size[u];
}
void dfs2(LL u,LL now_top)
{
new_num[u]=++cnt;//访问顺序作为新编号
new_val[cnt]=val[u];
top[u]=now_top;
if(!mson[u]) return;
dfs2(mson[u],now_top);
for(LL i=head[u];i;i=next[i])
if(!new_num[vec[i]]) dfs2(vec[i],vec[i]);
return;
}
void build(LL l,LL r,LL p)
{
if(l==r) {w[p]=new_val[l];return;}
LL mid=(l+r)>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
w[p]=w[p<<1]+w[p<<1|1];
return;
}
void down(LL l,LL r,LL p)
{
if(!tag[p]) return;
LL mid=(l+r)>>1;
w[p<<1]+=(mid-l+1)*tag[p];
w[p<<1|1]+=(r-mid)*tag[p];
tag[p<<1]+=tag[p];
tag[p<<1|1]+=tag[p];
tag[p]=0;
return;
}
void p_add(LL l,LL r,LL p,LL x,LL v)
{
if(l==r) {w[p]+=v;return;}
down(l,r,p);
LL mid=(l+r)>>1;
if(x<=mid) p_add(l,mid,p<<1,x,v);
else p_add(mid+1,r,p<<1|1,x,v);
w[p]=w[p<<1|1]+w[p<<1];
return;
}
void sum_add(LL l,LL r,LL p,LL x,LL y,LL v)
{
if(x<=l&&y>=r)
{
w[p]+=(r-l+1)*v;
tag[p]+=v;
return;
}
down(l,r,p);
LL mid=(l+r)>>1;
if(x<=mid) sum_add(l,mid,p<<1,x,y,v);
if(y>mid) sum_add(mid+1,r,p<<1|1,x,y,v);
w[p]=w[p<<1]+w[p<<1|1];
return;
}
long long query(LL l,LL r,LL p,LL x,LL y)
{
long long ans=0;
if(l>=x&&r<=y) return w[p];
down(l,r,p);
LL mid=(l+r)>>1;
if(x<=mid) ans+=query(l,mid,p<<1,x,y);
if(y>mid) ans+=query(mid+1,r,p<<1|1,x,y);
return ans;
}
long long t_query(LL x,LL y)
{
long long ans=0;
while(top[x]!=top[y])
{
if(depth[top[x]]<depth[top[y]]) swap(x,y);
ans+=query(1,n,1,new_num[top[x]],new_num[x]);
x=f[top[x]];
}
if(depth[x]>depth[y]) swap(x,y);
ans+=query(1,n,1,new_num[x],new_num[y]);
return ans;
}
int main()
{
LL x,y,op;
scanf("%lld%lld",&n,&m);
for(LL i=1;i<=n;i++) scanf("%lld",&val[i]);
for(LL i=1;i<n;i++)
{
scanf("%lld%lld",&x,&y);
add(x,y);add(y,x);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,n,1);
while(m--)
{
scanf("%lld",&op);
if(op==1)
{
scanf("%lld %lld",&x,&y);
p_add(1,n,1,new_num[x],y);
}
if(op==2)
{
scanf("%lld %lld",&x,&y);
sum_add(1,n,1,new_num[x],new_num[x]+size[x]-1,y);
}
if(op==3)
{
scanf("%lld",&x);
printf("%lld\n",t_query(1,x));
}
}
return 0;
}
回复
共 54 条回复,欢迎继续交流。
正在加载回复...