洛谷模板
#include<bits/stdc++.h>
using namespace std;
const int M=500500;
struct TREE{int l,r,w,lz;}t[M<<2];
struct EDGE{int v,next;}e[M];
int head[M],edget,n,m,r,mod,w[M];
int deep[M],fa[M],son[M],siz[M]; //节点的深度 节点的父亲 节点的重儿子 节点子树的大小
int top[M],idn[M],cnt,val[M]; //节点所在重链的头节点 节点新的编号 新编号为i的点的点权
void add(int,int); //加边进入邻接表
int dfs1(int,int,int); //求每个节点的深度、重儿子和dfs序
void dfs2(int,int); //对整个树进行重新编号
void build(int,int,int); //建树
void update(int); //更新节点值
void IntervalAdd(int,int,int,int); //区间加
int IntervalSum(int,int,int); //区间求和
void down(int); //下推标记
void TreeSum(int,int); //求x到y路径上的和
void TreeAdd(int,int,int); //给x到y路径上的每一个点加val权值
int main(){
ios::sync_with_stdio(false);
register int i;
int x,y,z;
char q;
cin>>n>>m>>r>>mod;
for(i=1;i<=n;++i) cin>>w[i];
for(i=1;i<n;++i){
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,n,1);
for(i=1;i<=m;++i){
cin>>q;
switch(q){
case '1':{cin>>x>>y>>z; TreeAdd(x,y,z); break;}
case '2':{cin>>x>>y; TreeSum(x,y); break;}
case '3':{cin>>x>>z; IntervalAdd(1,idn[x],idn[x]+siz[x]-1,z); break;}
case '4':{cin>>x; printf("%d\n",IntervalSum(1,idn[x],idn[x]+siz[x]-1)%mod); break;}
}
}
return 0;
}
void add(int x,int y){
e[++edget].v=y;
e[edget].next=head[x];
head[x]=edget;
}
int dfs1(int x,int f,int dp){
fa[x]=f;
deep[x]=dp;
siz[x]=1;
int maxsiz=-1;
for(register int i=head[x];i;i=e[i].next){
if(e[i].v==f) continue;
siz[x]+=dfs1(e[i].v,x,dp+1);
if(siz[e[i].v]>maxsiz){ //修改重儿子
son[x]=e[i].v;
maxsiz=siz[e[i].v];
}
}
return siz[x];
}
void dfs2(int x,int topx){ //topx表示节点x所在重链的头节点
top[x]=topx;
idn[x]=++cnt;
val[cnt]=w[x];
if(!son[x]) return;
dfs2(son[x],topx);
for(register int i=head[x];i;i=e[i].next) if(!idn[e[i].v]) dfs2(e[i].v,e[i].v);
}
void build(int l,int r,int u){
t[u].l=l,t[u].r=r;
if(l==r){
t[u].w=val[l];
return;
}
int m=(l+r)>>1;
build(l,m,u<<1);
build(m+1,r,u<<1|1);
update(u);
}
void update(int u){
t[u].w=(t[u<<1].w+t[u<<1|1].w+mod)%mod;
}
void IntervalAdd(int u,int l,int r,int val){
if(t[u].l>=l && t[u].r<=r){
t[u].w+=(t[u].r-t[u].l+1)*val;
t[u].lz+=val;
return;
}
if(t[u].lz) down(u);
int m=(t[u].l+t[u].r)>>1;
if(m>=l) IntervalAdd(u<<1,l,r,val);
if(m<r) IntervalAdd(u<<1|1,l,r,val);
update(u);
}
int IntervalSum(int u,int l,int r){
int ans=0;
if(t[u].l>=l && t[u].r<=r) return t[u].w;
if(t[u].lz) down(u);
int m=(t[u].l+t[u].r)>>1;
if(m>=l) ans=(ans+IntervalSum(u<<1,l,r))%mod;
if(m<r) ans=(ans+IntervalSum(u<<1|1,l,r))%mod;
return ans;
}
void down(int u){
t[u<<1].lz+=t[u].lz;
t[u<<1|1].lz+=t[u].lz;
t[u<<1].w=(t[u<<1].w+(t[u<<1].r-t[u<<1].l+1)*t[u].lz)%mod;
t[u<<1|1].w=(t[u<<1|1].w+(t[u<<1|1].r-t[u<<1|1].l+1)*t[u].lz)%mod;
t[u].lz=0;
}
void TreeSum(int x,int y){
int ans=0;
while(top[x]!=top[y]){ //当x和y不在同一重链上时,先跳到同一条重链上
if(deep[top[x]]<deep[top[y]]) swap(x,y); //把深度深的向上跳
ans=(ans+IntervalSum(1,idn[top[x]],idn[x]))%mod; //直接跳到fa[top[x]],并记录权值和
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y); //线段树的操作区间[l,r]要满足l<=r
ans=(ans+IntervalSum(1,idn[x],idn[y]))%mod;
printf("%d\n",ans);
}
void TreeAdd(int x,int y,int val){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
IntervalAdd(1,idn[top[x]],idn[x],val);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
IntervalAdd(1,idn[x],idn[y],val);
} 树的统计
#include<bits/stdc++.h>
using namespace std;
const int M=500500;
struct EDGE{int v,next;}e[M];
struct TREE{int l,r,w,maxn,lz;}t[M<<2];
int n,w[M],head[M],num,q,deep[M],cnt;
int fa[M],top[M],idn[M],siz[M],son[M],val[M];
string s;
inline void add(int,int);
int dfs1(int,int,int);
inline void dfs2(int,int);
inline void build(int,int,int);
inline void update(int);
int IntervalSum(int,int,int);
int IntervalMax(int,int,int);
inline void SinglepointChange(int,int,int);
inline void TreeSum(int,int);
inline void TreeMax(int,int);
int main(){
ios::sync_with_stdio(0);
register int i,j;
int x,y;
cin>>n;
for(i=1;i<n;++i){
cin>>x>>y;
add(x,y);
add(y,x);
}
for(i=1;i<=n;++i) cin>>w[i];
dfs1(1,0,1);
dfs2(1,1);
build(1,n,1);
cin>>q;
for(i=1;i<=q;++i){
cin>>s>>x>>y;
if(s=="CHANGE") SinglepointChange(1,x,y);
else if(s=="QMAX") TreeMax(x,y);
else TreeSum(x,y);
}
return 0;
}
inline void add(int x,int y){
e[++num].v=y;
e[num].next=head[x];
head[x]=num;
}
int dfs1(int x,int f,int dp){
fa[x]=f;
deep[x]=dp;
siz[x]=1;
int maxsiz=-1;
for(register int i=head[x];i;i=e[i].next){
if(e[i].v==f) continue;
siz[x]+=dfs1(e[i].v,x,dp+1);
if(siz[e[i].v]>maxsiz){
son[x]=e[i].v;
maxsiz=siz[e[i].v];
}
}
return siz[x];
}
inline void dfs2(int x,int topx){
idn[x]=++cnt;
top[x]=topx;
val[cnt]=w[x];
if(!son[x]) return;
dfs2(son[x],topx);
for(register int i=head[x];i;i=e[i].next) if(!idn[e[i].v]) dfs2(e[i].v,e[i].v);
}
inline void build(int l,int r,int u){
t[u].l=l,t[u].r=r;
if(l==r){
t[u].w=t[u].maxn=val[l];
return;
}
int m=(l+r)>>1;
build(l,m,u<<1);
build(m+1,r,u<<1|1);
update(u);
}
inline void update(int u){
t[u].w=t[u<<1].w+t[u<<1|1].w;
t[u].maxn=max(t[u<<1].maxn,t[u<<1|1].maxn);
}
int IntervalSum(int u,int l,int r){
int sum=0;
if(t[u].l>=l && t[u].r<=r) return t[u].w;
int m=(t[u].l+t[u].r)>>1;
if(m>=l) sum+=IntervalSum(u<<1,l,r);
if(m<r) sum+=IntervalSum(u<<1|1,l,r);
return sum;
}
int IntervalMax(int u,int l,int r){
int maxn=-1000000000;
if(t[u].l>=l && t[u].r<=r) return t[u].maxn;
int m=(t[u].l+t[u].r)>>1;
if(m>=l) maxn=max(maxn,IntervalMax(u<<1,l,r));
if(m<r) maxn=max(maxn,IntervalMax(u<<1|1,l,r));
return maxn;
}
inline void SinglepointChange(int u,int x,int val){
if(t[u].l==idn[x] && t[u].r==idn[x]){
t[u].w=t[u].maxn=val;
return;
}
int m=(t[u].l+t[u].r)>>1;
if(m>=idn[x]) SinglepointChange(u<<1,x,val);
if(m<idn[x]) SinglepointChange(u<<1|1,x,val);
update(u);
}
inline void TreeSum(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=IntervalSum(1,idn[top[x]],idn[x]);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
ans+=IntervalSum(1,idn[x],idn[y]);
printf("%d\n",ans);
}
inline void TreeMax(int x,int y){
int maxn=-1000000000;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) swap(x,y);
maxn=max(maxn,IntervalMax(1,idn[top[x]],idn[x]));
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
maxn=max(maxn,IntervalMax(1,idn[x],idn[y]));
printf("%d\n",maxn);
} 树上操作
#include<bits/stdc++.h>
using namespace std;
const int M = 500500;
typedef long long ll;
struct EDGE{ll v,next;} e[M << 2];
struct TREE{ll l,r,lz; ll w;} t[M << 2];
ll n,m,head[M << 2],num,w[M],fa[M],top[M];
ll idn[M],val[M],son[M],siz[M],deep[M],cnt;
void add(ll,ll);
ll dfs1(ll,ll,ll);
void dfs2(ll,ll);
void build(ll,ll,ll);
void update(ll);
void down(ll);
void SinglepointAdd(ll,ll,ll);
void IntervalAdd(ll,ll,ll,ll);
ll IntervalSum(ll,ll,ll);
void TreeSum(ll x,ll y);
int main(){
ios::sync_with_stdio(false);
register int i,j;
ll q,x,y;
cin >> n >> m;
for(i = 1; i <= n; ++i) cin >> w[i];
for(i = 1; i < n; ++i){
cin >> x >> y;
add(x, y);
add(y, x);
}
dfs1(1, 0, 1);
dfs2(1, 1);
build(1, n, 1);
for(i = 1; i <= m; ++i){
cin >> q;
if(q == 1){
cin >> x >> y;
SinglepointAdd(1, idn[x], y);
}
else if(q == 2){
cin >> x >> y;
IntervalAdd(1, idn[x], idn[x]+siz[x]-1, y);
}
else{
cin >> x;
TreeSum(1, x);
}
}
return 0;
}
void add(ll x,ll y){
e[++num].v = y;
e[num].next = head[x];
head[x] = num;
}
ll dfs1(ll now,ll f,ll dp){
fa[now] = f;
deep[now] = dp;
siz[now] = 1;
ll maxson = -1;
for(register int i = head[now]; i; i = e[i].next){
if(f == e[i].v) continue;
siz[now] += dfs1(e[i].v, now, dp+1);
if(maxson < siz[e[i].v]){
maxson = siz[e[i].v];
son[now] = e[i].v;
}
}
return siz[now];
}
void dfs2(ll now,ll topx){
idn[now] = ++cnt;
top[now] = topx;
val[cnt] = w[now];
if(!son[now]) return;
dfs2(son[now], topx);
for(register int i = head[now]; i; i = e[i].next) if(!idn[e[i].v]) dfs2(e[i].v, e[i].v);
}
void build(ll l,ll r,ll u){
t[u].l = l,t[u].r = r;
if(l == r){
t[u].w = val[l];
return;
}
ll m = (l + r) >> 1;
build(l, m, u<<1);
build(m+1, r, u<<1|1);
update(u);
}
void update(ll u){
t[u].w = t[u << 1].w + t[u << 1 | 1].w;
}
void down(ll u){
t[u << 1].lz += t[u].lz;
t[u << 1 | 1].lz += t[u].lz;
t[u << 1].w += (t[u << 1].r - t[u << 1].l + 1) * t[u].lz;
t[u << 1 | 1].w += (t[u << 1 | 1].r - t[u << 1 | 1].l + 1) * t[u].lz;
t[u].lz = 0;
}
void SinglepointAdd(ll u,ll x,ll add){
if(t[u].l == x && t[u].l == t[u].r){
t[u].w += add;
return;
}
if(t[u].lz) down(u);
ll m = (t[u].l + t[u].r) >> 1;
if(m >= x) SinglepointAdd(u << 1, x, add);
if(m < x) SinglepointAdd(u << 1 | 1, x, add);
update(u);
}
void IntervalAdd(ll u,ll l,ll r,ll add){
if(t[u].l >= l && t[u].r <= r){
t[u].w += (t[u].r - t[u].l + 1) * add;
t[u].lz += add;
return;
}
if(t[u].lz) down(u);
ll m = (t[u].l + t[u].r) >> 1;
if(m >= l) IntervalAdd(u << 1, l, r, add);
if(m < r) IntervalAdd(u << 1 | 1, l, r, add);
update(u);
}
ll IntervalSum(ll u,ll l,ll r){
ll ans=0;
if(t[u].l >= l && t[u].r <= r) return t[u].w;
if(t[u].lz) down(u);
ll m = (t[u].l + t[u].r) >> 1;
if(m >= l) ans += IntervalSum(u << 1, l, r);
if(m < r) ans += IntervalSum(u << 1 | 1, l, r);
return ans;
}
void TreeSum(ll x,ll y){
ll ans = 0;
while(top[x] != top[y]){
if(deep[top[x]] < deep[top[y]]) swap(x,y);
ans += IntervalSum(1, idn[top[x]], idn[x]);
x = fa[top[x]];
}
if(deep[x] > deep[y]) swap(x,y);
ans += IntervalSum(1,idn[x],idn[y]);
printf("%lld\n",ans);
}
京公网安备 11010502036488号