见https://www.luogu.org/record/lists?pid=P3384&uid=&flag=&page=2
wa了一晚上,原来是跳链时的维护反了边，详见代码，哈哈，终于ac了，不容易啊
#include<cstdio> #include<cstdlib> #include<iostream> #define M 110000 #define LL long long #define reg register #define REP(i,a,b) for(int i=(int)a; i<=(int)b; ++i) #define NODES(i,h,a,b) for(int i=a[h]; i; i=b[i]) using namespace std; int cnt, gen; int bgn[M], to[M<<1], nxt[M<<1]; LL w[M]; int siz[M], fa[M], top[M], son[M], dep[M]; int ru[M], chu[M]; LL sum[M<<2], addv[M<<2]; int ti, e; LL mod; int n, m; LL asksum; void edge(int x,int y) {to[e]=y; nxt[e]=bgn[x]; bgn[x]=e; ++e;} struct Chain { void line(int h, int g, int dep_) { siz[h] = 1; son[h] = 0; fa[h] = g; dep[h] = dep_; NODES(i,h,bgn,nxt) { int y = to[i]; if(y == g) continue; line(y, h, dep_+1); siz[h] += siz[y]; if(siz[y] > siz[son[h]]) son[h] = y; } } void zip(int h, int g) { top[h] = g; ru[h] = ++ti; if(son[h]) zip(son[h], g); NODES(i,h,bgn,nxt) { int y = to[i]; if(y == fa[h]) continue; if(y == son[h]) continue; zip(y, y); } chu[h] = ti; } void getchain() { line(gen, gen, 1); zip(gen, gen); } void maintain(int h, int l, int r) { if(l < r) { sum[h] = (sum[(h<<1)] + sum[(h<<1)|1]) % mod; } if(addv[h]) { sum[h] = (sum[h] + (LL)(r - l + 1) * addv[h]) % mod; } if(l == r) addv[h] = 0LL; } void pushdown(int h) { if(addv[h]) { addv[h<<1] += addv[h]; addv[h<<1] %= mod; addv[(h<<1)|1] += addv[h]; addv[(h<<1)|1] %= mod; addv[h] = 0LL; } } void add(int h,int l,int r,int y1,int y2,LL v) { if(y1 <= l && r <= y2) { addv[h] += v; addv[h] %= mod; } else { pushdown(h); int m = (l + r) >> 1; if(y1 <= m) add((h<<1), l, m, y1, y2, v); else maintain((h<<1),l,m); if(m < y2) add((h<<1)|1,m+1,r, y1, y2, v);else maintain((h<<1)|1,m+1,r); } maintain(h, l, r); } void query(int h,int l,int r,int y1,int y2,LL add_) { if(y1 <= l && r <= y2) { LL p = sum[h] + ((add_) * (LL)(min(r, y2) - max(l, y1) + 1)) % mod; asksum += p; asksum %= mod; } else { int m = (l + r) >> 1; if(y1 <= m) query(h<<1, l, m, y1, y2, add_+addv[h]); if(m < y2) query((h<<1)|1, m+1, r, y1, y2, add_+addv[h]); } } void getSegmenttree() { for(int i=1; i<=n; ++i) { add(1, 1, n, ru[i], ru[i], w[i]); } asksum = 0; } void askson(int h) { asksum = 0; query(1, 1, n, ru[h], chu[h], 0); asksum%=mod; printf("%lld\n",asksum); } void addson(int h,int v) { add(1, 1, n, ru[h], chu[h], v); } void askroad(int x,int y) { asksum = 0; while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); query(1, 1, n, ru[top[x]], ru[x], 0); asksum%=mod; x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x, y); query(1, 1, n, ru[x], ru[y], 0); asksum%=mod; printf("%lld\n",asksum); } void addroad(int x,int y,int v) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); add(1, 1, n, ru[top[x]], ru[x], v); asksum%=mod; x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x, y); add(1, 1, n, ru[x], ru[y], v); asksum%=mod; } void work(int m) { getchain(); getSegmenttree(); int ord, x, y; LL z; while(m--) { scanf("%d",&ord); //printf("%d\n",ord); if(ord == 1) { scanf("%d%d%lld",&x,&y,&z); addroad(x, y, z);} if(ord == 2) { scanf("%d%d",&x,&y); askroad(x, y);} if(ord == 3) { scanf("%d%lld",&x,&z); addson(x, z);} if(ord == 4) { scanf("%d",&x); askson(x);} } } } tree; int main() { int x, y, z; //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d%d%d%lld",&n,&m,&gen,&mod); REP(i, 1, n) scanf("%lld",&w[i]); REP(i, 1, n-1) { scanf("%d%d",&x,&y); edge(x, y); edge(y, x); } tree.work(m); }