@[秋水1024](/user/233972) 你在`push`函数里,对线段树的两个儿子访问的时候,注意,`+`的优先级比`<<`高,所以应该写成`<<1|1`或者`*2+1`,如果还有,同理。
此外,不保证没错误了
如果还有就at我
by 一E孤行 @ 2021-10-02 16:58:21
```
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#define ll long long
using namespace std;
const int N=100086;
int m,n,r,u0,v0;
int fa[N],dep[N],size[N],son[N],top[N],seg[N],rev[N],tot;
int f[4*N],laz[4*N],c[4*N],a[N],p;
vector<int>e[N];
ll read(){
ll x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x;
}
void dfs1(int u,int f){
int v;
size[u]=1;
fa[u]=f;
dep[u]=dep[f]+1;
for(int i=0;i<e[u].size();i++){
v=e[u][i];
if(v==f)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int f){
int v;
if(son[u]){
v=son[u];
seg[v]=++tot;
rev[tot]=v;
top[v]=top[u];
dfs2(v,u);
}
for(int i=0;i<e[u].size();i++){
v=e[u][i];
if(v==f)continue;
if(!top[v]){
seg[v]=++tot;
rev[tot]=v;
top[v]=v;
dfs2(v,u);
}
}
}
void build(int k,int l,int r){
if(l==r){f[k]=a[rev[l]];return;}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
f[k]=(f[k<<1]+f[k<<1|1])%p;
}
void add(int k,int l,int r,ll v){
laz[k]=(laz[k]+v)%p;
f[k]=(f[k]+((r-l+1)*v)%p)%p;return;
}
void push(int k,int l,int r){
if(laz[k]==0)return;
int mid=(l+r)>>1;
add(k<<1,l,mid,laz[k]);
add(k<<1|1,mid|1,r,laz[k]);
laz[k]=0;return;
}
void modadd(int k,int l,int r,int x,int y,ll v){
if(x<r||y>l)return;
if(x<=l&&y>=r)return add(k,l,r,v);
int mid=(l+r)>>1;
push(k,l,r);
if(x<=mid)modadd(k<<1,l,mid,x,y,v);
if(mid<y)modadd(k<<1|1,mid+1,r,x,y,v);
f[k]=f[k<<1]+f[k<<1|1];
}
ll modsum(int k,int l,int r,int x,int y){
if(x<r||y>l)return 0;
if(x<=l&&y>=r)return f[k];
int mid=(l+r)>>1,sum=0;
push(k,l,r);
if(x<=mid)sum=(sum+modsum(k<<1,l,mid,x,y))%p;
if(y>mid)sum=(sum+modsum(k<<1|1,mid+1,r,x,y))%p;
return sum;
}
void linadd(int x,int y,ll v){
while(top[x]!=top[y]){
if(dep[x]<dep[y])swap(x,y);
modadd(1,1,tot,seg[x],seg[top[x]],v);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
modadd(1,1,tot,seg[x],seg[y],v);
}
void sonadd(int k,ll v){
return modadd(1,1,tot,rev[k],rev[k]+size[k]-1,v);
}
ll linsum(int x,int y){
ll sum=0;
while(top[x]!=top[y]){
if(dep[x]<dep[y])swap(x,y);
sum=(sum+modsum(1,1,tot,seg[x],seg[top[x]]))%p;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
sum=(sum+modsum(1,1,tot,seg[x],seg[y]))%p;
return sum;
}
ll sonsum(ll k){
return modsum(1,1,tot,rev[k],rev[k]+size[k]-1);
}
int main()
{
cin>>n>>m>>r>>p;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++){
cin>>u0>>v0;e[u0].push_back(v0);
e[v0].push_back(u0);
}
int nn,w0;
top[1]=1;
dfs1(1,0);
dfs2(1,0);
build(1,1,n);
for(ll i=1;i<=m;i++){
cin>>nn;
if(nn==1){
cin>>u0>>v0>>w0;
linadd(u0,v0,w0);
}
if(nn==3){
cin>>u0>>w0;
sonadd(u0,w0);
}
if(nn==2){
cin>>u0>>v0;
cout<<linsum(u0,v0)<<endl;
}
if(nn==4){
cin>>u0;
cout<<sonsum(u0)<<endl;
}
}
return 0;
}
```
还是不行
阿巴阿巴阿巴
@[一E孤行](/user/229919)
by 秋水1024 @ 2021-10-02 18:06:07
@[秋水1024](/user/233972) seg数组和rev数组分别代表什么哇
by 一E孤行 @ 2021-10-02 18:41:26
@[秋水1024](/user/233972) debuging,我觉得你写的很奇怪,很多错的,`dfs2`我不确保是对的,因为我没见过这么写的(
我用你的变量名再给你重构一遍您看看
by 1egxの小舔狗 @ 2021-10-02 19:20:28
@[1egxの小舔狗](/user/139819) 谢谢 您
by 秋水1024 @ 2021-10-02 19:40:48
@[一E孤行](/user/229919) 我觉得好像rev是点在线段树的位置
而且在线段树上rev[seg[i]]=i;
by 秋水1024 @ 2021-10-02 19:50:43
@[秋水1024](/user/233972) 你的rev和seg没有搞清楚的,rev只在建树的时候会用到的,seg指的是dfs序,rev只是dfs序对应的数字
by 一E孤行 @ 2021-10-02 19:55:53
@[秋水1024](/user/233972) [link](https://www.luogu.com.cn/paste/zym1u80g)
大致是这样,但是RE掉了,我再调一下(
by 1egxの小舔狗 @ 2021-10-02 20:56:34
@[秋水1024](/user/233972)
然后AC Code可以参考这个(我今天写的P3178,应该就只有那个查询路径不大一样):
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
using namespace std;
#define maxn 1000005
#define int long long
struct aaa{
int to,nxt;
}a[maxn<<1];
struct tree{
int l,r,sum,tag;
}t[maxn<<2];
int n,m;
int head[maxn],top[maxn],tot,cnt,son[maxn],siz[maxn],dfn[maxn];
void add(int x,int y) {
a[tot].to=y;
a[tot].nxt=head[x];
head[x]=tot++;
}
int fa[maxn],dep[maxn];
void dfs1(int u,int f) {
fa[u]=f;
dep[u]=dep[f]+1;
siz[u]=1;
int maxsiz=0;
for(int i=head[u];i!=-1;i=a[i].nxt) {
int v=a[i].to;
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v] > maxsiz) {
maxsiz=siz[v];
son[u]=v;
}
}
}
int val[maxn],wl[maxn];
void dfs2(int u,int t) {
dfn[u]=++cnt;
wl[cnt]=val[u];
top[u]=t;
if(son[u]) dfs2(son[u],t);
for(int i=head[u];i!=-1;i=a[i].nxt) {
int v=a[i].to;
if(v==fa[u] || v==son[u]) continue;
dfs2(v,v);
}
}
void update(int id) {
t[id].sum=t[id<<1].sum+t[id<<1|1].sum;
}
void build(int id,int l,int r) {
t[id].l=l;
t[id].r=r;
if(l==r) {
t[id].sum=wl[l];
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
update(id);
}
void push_down(int id) {
if(t[id].tag==0) return;
t[id<<1].sum+=(t[id<<1].r-t[id<<1].l+1)*t[id].tag;
t[id<<1].tag+=t[id].tag;
t[id<<1|1].sum+=(t[id<<1|1].r-t[id<<1|1].l+1)*t[id].tag;
t[id<<1|1].tag+=t[id].tag;
t[id].tag=0;
}
void modify(int id,int x,int y,int z) {
int l=t[id].l,r=t[id].r;
if(x<=l && r<=y) {
t[id].tag+=z;
t[id].sum+=(r-l+1)*z;
return;
}
push_down(id) ;
int mid=(l+r)>>1;
if(x<=mid) modify(id<<1,x,y,z);
if(y>mid) modify(id<<1|1,x,y,z);
update(id);
}
int query(int id,int x,int y) {
int l=t[id].l,r=t[id].r;
if(x<=l && r<=y) {
return t[id].sum;
}
push_down(id);
int mid=(l+r)>>1;
int ans=0;
if(x<=mid) ans+=query(id<<1,x,y);
if(y>mid) ans+=query(id<<1|1,x,y);
return ans;
}
int getsum(int x) {
int res=0;
while(top[x] != 1) {
res+=query(1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
res+=query(1,dfn[1],dfn[x]);
return res;
}
void dfs ( int k )
{
cout << t [ k ] .l << " - " << t [ k ] .r << " : " << t [ k ] .sum << endl ;
if ( t [ k ] .l == t [ k ] .r )
return ;
push_down ( k ) ;
// int mid = ( t [ k ] .l + t [ k ] .r ) >> 1 ;
dfs ( k << 1 ) ;
dfs ( k << 1 | 1 ) ;
}
signed main() {
int c1=clock();
#ifdef LOCAL
freopen("in.in","r",stdin);
freopen("out.ans","w",stdout);
#endif
//=========================================
memset(head,-1,sizeof(head));
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%lld",&val[i]);
}
for(int i=1;i<n;i++) {
int x,y;
scanf("%lld%lld",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
// cout << " val : " ;
// for ( int i = 1 ; i <= n ; ++ i )
// cout << val [ i ] << " " ;
// cout << endl << " dfn : " ;
// for ( int i = 1 ; i <= n ; ++ i )
// cout << dfn [ i ] << " " ;
// cout << endl << " wl : " ;
// for ( int i = 1 ; i <= n ; ++ i )
// cout << wl [ i ] << " " ;
// cout << endl << " top : " ;
// for ( int i = 1 ; i <= n ; ++ i )
// cout << top [ i ] << " " ;
// cout << endl ;
// dfs ( 1 ) ;
for(int i=1;i<=m;i++) {
int opt,x,y;
scanf("%lld",&opt);
if(opt==1) {
scanf("%lld%lld",&x,&y);
modify(1,dfn[x],dfn[x],y);
}
if(opt==2) {
scanf("%lld%lld",&x,&y);
modify(1,dfn[x],dfn[x]+siz[x]-1,y);
}
if(opt==3) {
scanf("%lld",&x);
printf("%lld\n",getsum(x));
}
// dfs ( 1 ) ;
// cout << endl << endl ;
}
//=========================================
cerr<<"Tmie Used:"<<clock()-c1<<"ms"<<endl;
return 0;
}
```
by 1egxの小舔狗 @ 2021-10-02 21:09:47
@[秋水1024](/user/233972) 我上面云剪切板里的路径查询“应该”是对的,然后你写的那个有点问题(
by 1egxの小舔狗 @ 2021-10-02 21:11:43