RT, 本地第二个点跑了1min 求助orz

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#define Wild_Donkey 0
using namespace std;
inline unsigned int RD() {
  char ich(getchar());
  unsigned int intmp(0);
  while ((ich < '0') || (ich > '9')) {
    ich = getchar();
  }
  while ((ich <= '9') && (ich >= '0')) {
    intmp *= 10;
    intmp += ich - '0';
    ich = getchar();
  }
  //  printf("RD %d\n", intmp);
  return intmp;
}
unsigned int m, n, Rot, cntd(0), DW;
unsigned int Mod, a[200005], C, A, B, yl, yr, yv;
struct Edge;
struct Node {
  unsigned int Siz, Dep, Cntson, DFSr;
  unsigned int Val;
  Node *Fa, *Top, *Hvy;
  Edge *Fst;
} N[200005];
struct Edge {
  Edge *Nxt;
  Node *To;
} E[400005], *cnte(E);
void Lnk(Node *x, Node *y) {
  //  printf("Lnk %d %d\n", x - N, y - N);
  (++cnte)->Nxt = x->Fst;
  x->Fst = cnte;
  cnte->To = y;
  return;
}
struct SgNode {
  unsigned int Val, Tag;
  SgNode *L, *R;
} SgN[400005], *cntn(SgN);
void SgBld(SgNode *x, const unsigned int &l, const unsigned int &r) {
  x->Tag = 0;
  if (l == r) {
    x->Val = a[l];
    x->L = x->R = NULL;
    return;
  }
  x->L = ++cntn;
  x->R = ++cntn;
  int mid((l + r) >> 1);
  SgBld(x->L, l, mid);
  SgBld(x->R, mid + 1, r);
  x->Val = x->L->Val + x->R->Val;
  return;
}
inline void PsDw(SgNode *x, const unsigned int &l, const unsigned int &r) {
  unsigned int mid((l + r) >> 1);
  if (mid < r) {
    x->L->Val += x->Tag * (mid - l + 1);
    x->R->Val += x->Tag * (r - mid);
    x->L->Tag += x->Tag;
    x->R->Tag += x->Tag;
  }
  x->Tag = 0;
  return;
}
inline void Udt(SgNode *x) {
  if (x->L) {
    x->Val = (x->L->Val + x->R->Val) % Mod;
  }
  return;
}
void SgChg(SgNode *x, const unsigned int &l, const unsigned int &r) {
  if (l == r) {
    x->Val += yv;
    return;
  }
  if ((l >= yl && r <= yr)) {
    x->Tag += yv;
    x->Val += (r - l + 1) * yv % Mod;
    return;
  }
  unsigned int mid((l + r) >> 1);
  if (x->Tag) {
    PsDw(x, l, r);
  }
  if (mid >= yl) {
    SgChg(x->L, l, mid);
  }
  if (mid < yr) {
    SgChg(x->R, mid + 1, r);
  }
  Udt(x);
  return;
}
unsigned int SgQry(SgNode *x, const int &l, const int &r) {
  if (l >= yl && r <= yr) {
    return x->Val %= Mod;
  }
  if (l == r) {
    return Wild_Donkey;
  }
  if (x->Tag) {
    PsDw(x, l, r);
  }
  unsigned int mid((l + r) >> 1), Tmp(0);
  if (mid >= yl) {
    Tmp += SgQry(x->L, l, mid);
  }
  if (mid < yr) {
    Tmp += SgQry(x->R, mid + 1, r);
  }
  return Tmp % Mod;
}
void SonChg(Node *x) {
  yl = x->DFSr;
  yr = x->DFSr + x->Siz - 1;
  return SgChg(SgN, 1, n);
}
unsigned int SonQry(Node *x) {
  yl = x->DFSr;
  yr = x->DFSr + x->Siz - 1;
  return SgQry(SgN, 1, n);
}
void LnkChg(Node *x, Node *y) {
  while (x->Top != y->Top) {
    if (x->Top->Dep < y->Top->Dep) {
      swap(x, y);
    }
    yl = x->Top->DFSr;
    yr = x->DFSr;
    SgChg(SgN, 1, n);
    x = x->Top->Fa;
  }
  if (x->Dep < y->Dep) {
    yl = x->DFSr;
    yr = y->DFSr;
    return SgChg(SgN, 1, n);
  } else {
    yl = y->DFSr;
    yr = x->DFSr;
    return SgChg(SgN, 1, n);
  }
  return;
}
unsigned int LnkQry(Node *x, Node *y) {
  unsigned int Tmp(0);
  while (x->Top != y->Top) {
    if (x->Top->Dep < y->Top->Dep) {
      swap(x, y);
    }
    yl = x->Top->DFSr;
    yr = x->DFSr;
    Tmp += SgQry(SgN, 1, n);
    x = x->Top->Fa;
  }
  if (x->Dep < y->Dep) {
    yl = x->DFSr;
    yr = y->DFSr;
    Tmp += SgQry(SgN, 1, n);
  } else {
    yl = y->DFSr;
    yr = x->DFSr;
    Tmp += SgQry(SgN, 1, n);
  }
  return Tmp % Mod;
}
void Bld(Node *x) {
  if (x->Fa) {
    x->Dep = x->Fa->Dep + 1;
  } else {
    x->Dep = 1;
  }
  x->Siz = 1;
  x->Cntson = 0;
  Edge *Sid(x->Fst);
  while (Sid) {
    if (Sid->To != x->Fa) {
      Sid->To->Fa = x;
      Bld(Sid->To);
      if (!(x->Hvy)) {
        x->Hvy = Sid->To;
      } else {
        if (x->Hvy->Cntson < Sid->To->Cntson) {
          x->Hvy = Sid->To;
        }
      }
      x->Siz += Sid->To->Siz;
      ++(x->Cntson);
    }
    Sid = Sid->Nxt;
  }
  return;
}
void DFS(Node *x) {
  x->DFSr = (++cntd);
  Edge *Sid(x->Fst);
  if (x->Hvy) {
    x->Hvy->Top = x->Top;
    DFS(x->Hvy);
  } else {
    return;
  }
  while (Sid) {
    if (Sid->To != x->Fa && Sid->To != x->Hvy) {
      Sid->To->Top = Sid->To;
      DFS(Sid->To);
    }
    Sid = Sid->Nxt;
  }
  return;
}
int main() {
  // double Ti(clock()), Mti(0);
  freopen("P3384_12.in", "r", stdin);
  freopen("P3384.out", "w", stdout);
  n = RD();
  m = RD();
  Rot = RD();
  Mod = RD();
  //  printf("n = %d m = %d Rot = %d Mod = %d\n", n, m, Rot, Mod);
  for (register int i(1); i <= n; ++i) {
    N[i].Val = RD() % Mod;
  }
  for (register int i(1); i < n; ++i) {
    A = RD();
    B = RD();
    Lnk(N + A, N + B);
    Lnk(N + B, N + A);
  }
  Bld(N + Rot);
  N[Rot].Top = N + Rot;
  DFS(N + Rot);
  for (register unsigned int i(1); i <= n; ++i) {
    a[N[i].DFSr] = N[i].Val;
  }
  SgBld(SgN, 1, n);
  // Ti = clock() - Ti;
  for (register unsigned int i(1); i <= m; ++i) {
    DW = RD();
    A = RD();
    // Ti = clock();
    switch (DW) {
      case 1: {
        B = RD();
        yv = RD() % Mod;
        LnkChg(N + A, N + B);
        break;
      }
      case 2: {
        B = RD();
        printf("%u\n", LnkQry(N + A, N + B));
        break;
      }
      case 3: {
        yv = RD() % Mod;
        SonChg(N + A);
        break;
      }
      case 4: {
        printf("%u\n", SonQry(N + A));
        break;
      }
      default: {
        printf("FYSNB\n");
        break;
      }
    }
    // Ti = clock() - Ti;
    // Mti = max(Mti, Ti);
  }
  // Ti = clock() - Ti;
  // printf("Time %lf MTime %lf\n", Ti, Mti);
  // system("pause");
  // fclose(stdin);
  // fclose(stdout);
  return 0;
}