Nowcoder练习赛26 E 树上路径

题意：一棵树，支持三种操作： - 子树加上一个值 - 路径加上一个值 - 询问一条路径上任取两个数的乘积的总和 ------------ 前两个操作好办，就是树剖模板 第三个操作让我联想到了P4247 序列操作 但是因为序列转移到了树上，所以没法直接套用 那不会是LCT吧？应该不是。。 其实很简单，我们只要树剖之后线段树维护**区间总和**和**区间平方和**就好了 因为最后的答案可以进行化简 比如说区间长度为3，三个数分别为$a,b,c$ 那么所求答案为$ab+ac+bc$ 经过一波操作可以发现ta其实是$[(a+b+c)^2-a^2-b^2-c^2]/2$ 其他情况同理 然后只要注意$pushdown$的时候区间加法对子区间的影响就好了 ~~还是Jan神NB啊~~ orzorz 贴上代码（取模不到位还WA了两发） ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=1e5+5,mod=1e9+7,inv2=5e8+4; struct node { int to,nxt; }edge[N<<1]; int n,m,num,head[N],fa[N],son[N],dep[N],tot[N]; int cnt,idx[N],top[N],a[N],w[N]; ll sum1[N<<2],sum2[N<<2],tag[N<<2]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num]=(node){to,head[from]}; head[from]=num; } void dfs(int k,int father,int deep) { int bigson=0; fa[k]=father; dep[k]=deep; tot[k]=1; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (v==father) continue; dfs(v,k,deep+1); tot[k]+=tot[v]; if (bigson<tot[v]) bigson=tot[v],son[k]=v; } } void dfs(int k,int tp) { idx[k]=++cnt; top[k]=tp; a[cnt]=k; if (!son[k]) return; dfs(son[k],tp); for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (!idx[v]) dfs(v,v); } } inline void pushup(int now) { sum1[now]=(sum1[now<<1]+sum1[now<<1|1])%mod; sum2[now]=(sum2[now<<1]+sum2[now<<1|1])%mod; } inline void pushdown(int now,int l,int r) { if (!tag[now]) return; tag[now<<1]=(tag[now<<1]+tag[now])%mod; tag[now<<1|1]=(tag[now<<1|1]+tag[now])%mod; sum2[now<<1]=(sum2[now<<1]+1ll*tag[now]*tag[now]*l+2ll*tag[now]*sum1[now<<1])%mod; sum2[now<<1|1]=(sum2[now<<1|1]+1ll*tag[now]*tag[now]*r+2ll*tag[now]*sum1[now<<1|1])%mod; sum1[now<<1]=(sum1[now<<1]+1ll*tag[now]*l)%mod; sum1[now<<1|1]=(sum1[now<<1|1]+1ll*tag[now]*r)%mod; tag[now]=0; } void build(int l,int r,int now) { if (l==r) { sum1[now]=1ll*w[a[l]]%mod; sum2[now]=1ll*w[a[l]]*w[a[l]]%mod; return; } int mid=(l+r)>>1; build(l,mid,now<<1); build(mid+1,r,now<<1|1); pushup(now); } void inchange(int L,int R,int l,int r,int now,int c) { if (l>R||r<L) return; if (l>=L&&r<=R) { sum2[now]=(sum2[now]+1ll*c*c*(r-l+1)+2ll*c*sum1[now])%mod; sum1[now]=(sum1[now]+1ll*c*(r-l+1))%mod; tag[now]=(tag[now]+c)%mod; return; } int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid); if (mid>=R) inchange(L,R,l,mid,now<<1,c); else if (mid<L) inchange(L,R,mid+1,r,now<<1|1,c); else { inchange(L,mid,l,mid,now<<1,c); inchange(mid+1,R,mid+1,r,now<<1|1,c); } pushup(now); } ll ingetsum1(int L,int R,int l,int r,int now) { if (l>R||r<L) return 0; if (l>=L&&r<=R) return sum1[now]%mod; int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid); if (mid>=R) return ingetsum1(L,R,l,mid,now<<1); if (mid<L) return ingetsum1(L,R,mid+1,r,now<<1|1); return (ingetsum1(L,mid,l,mid,now<<1)+ingetsum1(mid+1,R,mid+1,r,now<<1|1))%mod; } ll ingetsum2(int L,int R,int l,int r,int now) { if (l>R||r<L) return 0; if (l>=L&&r<=R) return sum2[now]%mod; int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid); if (mid>=R) return ingetsum2(L,R,l,mid,now<<1); if (mid<L) return ingetsum2(L,R,mid+1,r,now<<1|1); return (ingetsum2(L,mid,l,mid,now<<1)+ingetsum2(mid+1,R,mid+1,r,now<<1|1))%mod; } inline void treechange(int x,int y,int val) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); inchange(idx[top[x]],idx[x],1,n,1,val); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); inchange(idx[x],idx[y],1,n,1,val); } inline ll treesum1(int x,int y) { ll ans=0; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans=(ans+ingetsum1(idx[top[x]],idx[x],1,n,1))%mod; x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans=(ans+ingetsum1(idx[x],idx[y],1,n,1))%mod; return ans; } inline ll treesum2(int x,int y) { ll ans=0; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans=(ans+ingetsum2(idx[top[x]],idx[x],1,n,1))%mod; x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans=(ans+ingetsum2(idx[x],idx[y],1,n,1))%mod; return ans; } int main() { n=read(),m=read(); for (reg int i=1;i<=n;w[i++]=read()); for (reg int i=1;i<n;i++) { int x=read(),y=read(); add_edge(x,y); add_edge(y,x); } dfs(1,0,1); dfs(1,1); build(1,n,1); while (m--) { int opt=read(),x=read(),y=read(); if (opt==1) inchange(idx[x],idx[x]+tot[x]-1,1,n,1,y); if (opt==2) treechange(x,y,read()); if (opt==3) { ll sum11=treesum1(x,y),sum22=treesum2(x,y); ll ans=((sum11*sum11-sum22)%mod*inv2%mod+mod)%mod; printf("%lld\n",ans); } } return 0; } ```