没调出来，明天搞。
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; const int N = 100005; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } struct edge { int nxt,r; } e[2 * N]; int n,m,r,cnt; int a[N],lst[N],p; int f[N],d[N],siz[N],son[N],rk[N]; int top[N],id[N],tree[4 * N]; int lazy[N],len = 0; void add(int x,int y) { e[++len].nxt = lst[x]; e[len].r = y; lst[x] = len; } void dfs1(int u,int fa,int depth) { f[u] = fa; d[u] = depth; siz[u] = 1; for(int k = lst[u];k;k = e[k].nxt) { int y = e[k].r; if(y == fa) continue; dfs1(y,u,depth + 1); siz[u] += siz[y]; if(siz[y] > siz[son[u]]) { son[u] = y; } } } void dfs2(int u,int t) { top[u] = t; id[u] = ++cnt; rk[cnt] = u; if(!son[u]) return; dfs2(son[u],t); for(int k = lst[u];k;k = e[k].nxt) { int y = e[k].r; if(y != son[u] && y != f[u]) dfs2(y,y); } } void push_down(int o,int l,int r) { lazy[o << 1] += lazy[o]; lazy[o << 1 | 1] += lazy[o]; int len = (r - l + 1); tree[o << 1] += lazy[o] * (len - len >> 1); tree[o << 1 | 1] += lazy[o] * (len >> 1); a[o << 1] %= p; a[o << 1 | 1] %= p; lazy[o] = 0; } void build(int o,int l,int r) { if(l == r) { tree[o] = a[rk[l]]; tree[o] %= p; return; } int mid = (l + r) >> 1; build(o << 1,l,mid); build(o << 1 | 1,mid + 1,r); push_down(o,l,r); } void up_num(int o,int l,int r,int x,int y,int w) { if(l == x && r == y) { tree[o] += w * (l - r + 1); lazy[o] += w; return; } int mid = (l + r) >> 1; push_down(o,l,r); if(mid < x) up_num(o << 1 | 1,mid + 1,r,x,y,w); else if(mid >= y) up_num(o << 1,l,mid,x,y,w); else { up_num(o << 1,l,mid,x,mid,w); up_num(o << 1 | 1,mid + 1,r,mid + 1,y,w); } tree[o] = tree[o << 1] + tree[o << 1 | 1]; tree[o] %= p; } int query(int o,int l,int r,int x,int y) { if(l == r && x == y) { return tree[o]; } int mid = (l + r) >> 1; if(mid >= y) return query(o << 1,l,mid,x,y); else if(mid < x) return query(o << 1 | 1,mid + 1,r,x,y); else { query(o << 1,l,mid,x,mid); query(o << 1 | 1,mid + 1,r,mid + 1,y); push_down(o,l,r); return tree[o]; } } int sum_mak(int x,int y) { int ans = 0,fx = top[x],fy = top[y]; while(fx != fy) { if(d[fx] >= d[fy]) { ans += query(1,1,n,id[fx],id[x]); x = f[fx]; } else { ans += query(1,1,n,id[fy],id[y]); y = f[fy]; } fx = top[x]; fy = top[y]; } if(id[x] <= id[y]) ans += query(1,1,n,id[x],id[y]); else ans += query(1,1,n,id[y],id[x]); return ans; } void updates(int x,int y,int c) { int fx = top[x],fy = top[y]; while(fx != fy) { if(d[fx] >= d[fy]) { up_num(1,1,n,id[fx],id[x],c); x = f[fx]; } else { up_num(1,1,n,id[fy],id[y],c); y = f[fy]; } fx = top[x]; fy = top[y]; } if(id[x] <= id[y]) up_num(1,1,n,id[x],id[y],c); else up_num(1,1,n,id[y],id[x],c); } int main() { read(n);read(m);read(r);read(p); duke(i,1,n) read(a[i]); duke(i,1,n - 1) { int x,y; read(x);read(y); add(x,y); add(y,x); } cnt = 0; dfs1(r,0,1); dfs2(r,r); cnt = 0; build(1,1,n); duke(i,1,m) { int op,x,y,z; read(op); if(op == 1) { read(x);read(y);read(z); updates(x,y,z); } else if(op == 2) { read(x);read(y); printf("%d ",sum_mak(x,y)); } else if(op == 3) { read(x);read(z); // cout<<x<<endl; up_num(1,1,n,id[x],id[x] + siz[x] - 1,z); } else { read(x); printf("%d ",query(1,1,n,id[x],id[x] + siz[x] - 1)); } } return 0; }