func_code_string: #include <bits/stdc++.h>   using namespace std;   const int N = 210000;   vector<int> p[N];   bool vis[N], inq[N];   int fa[N], froot[N], troot[N], size[N], q[N], powk[N], val[N], in0[N], out0[N],       in1[N], out1[N], n, jsb, goal, k, dep[N], inv[N];   inline int Pow(int a, int b) {     int c = 1;     for (; b; b >>= 1, a = a * 1ll * a % jsb)       if (b & 1) c = c * 1ll * a % jsb;     return c;   }   const int mo = 100007;   struct state {     int head[N], np[N], p[N], cnt[N];     int tot;     inline void clear() {       for (int i = (1); i <= (int)tot; i++) {         int x = p[i];         np[i] = cnt[i] = p[i] = 0;         x %= mo;         head[x] = 0;       }       tot = 0;     }     inline void add(int x) {       int pos = x % mo;       for (int u = head[pos]; u; u = np[u])         if (p[u] == x) {           cnt[u]++;           return;         }       tot++;       p[tot] = x;       cnt[tot] = 1;       np[tot] = head[pos];       head[pos] = tot;     }     inline int ask(int x) {       int pos = x % mo;       for (int u = head[pos]; u; u = np[u])         if (p[u] == x) {           return cnt[u];         }       return 0;     }   } cnt;   inline int getroot(int y) {     q[q[0] = 1] = y;     inq[y] = 1;     fa[y] = 0;     for (int i = (1); i <= (int)q[0]; i++) {       int x = q[i];       for (int j = (0); j <= (int)p[x].size() - 1; j++)         if (!inq[p[x][j]] && !vis[p[x][j]]) {           q[++q[0]] = p[x][j];           inq[p[x][j]] = 1;           fa[p[x][j]] = x;         }     }     int a, b;     b = 210000;     a = 0;     for (int i = (q[0]); i >= (int)1; i--) {       int x = q[i];       size[x] = 1;       int MA = -1;       for (int j = (0); j <= (int)p[x].size() - 1; j++)         if (inq[p[x][j]] && fa[x] != p[x][j] && !vis[p[x][j]]) {           size[x] += size[p[x][j]];           if (size[p[x][j]] > MA) MA = size[p[x][j]];         }       if (q[0] - size[x] > MA) MA = q[0] - size[x];       if (MA < b) {         b = MA;         a = x;       }     }     for (int i = (1); i <= (int)q[0]; i++) {       int x = q[i];       inq[x] = 0;     }     return a;   }   inline void Bfs1(int y) {     q[q[0] = 1] = y;     inq[y] = 1;     froot[y] = val[y];     troot[y] = val[y];     dep[y] = 0;     for (int i = (1); i <= (int)q[0]; i++) {       int x = q[i];       for (int j = (0); j <= (int)p[x].size() - 1; j++)         if (!inq[p[x][j]] && !vis[p[x][j]]) {           int d = p[x][j];           troot[d] = (troot[x] * 1ll * k + val[d]) % jsb;           dep[d] = dep[x] + 1;           froot[d] = (froot[x] + 1ll * powk[dep[d]] * val[d]) % jsb;           q[++q[0]] = d;           inq[d] = 1;         }     }     for (int i = (1); i <= (int)q[0]; i++) inq[q[i]] = 0;   }   inline void work(int rt, int y, int v) {     q[q[0] = 1] = y;     inq[y] = 1;     for (int i = (1); i <= (int)q[0]; i++) {       int x = q[i];       for (int j = (0); j <= (int)p[x].size() - 1; j++)         if (!inq[p[x][j]] && !vis[p[x][j]]) {           inq[p[x][j]] = 1;           q[++q[0]] = p[x][j];         }     }     for (int i = (1); i <= (int)q[0]; i++) cnt.add((froot[q[i]] + jsb) % jsb);     for (int i = (1); i <= (int)q[0]; i++) {       int x = q[i];       int key = powk[dep[x]] * 1ll * val[rt] % jsb;       key = (key + goal) % jsb;       key = (key - troot[x]) % jsb;       key = key * 1ll * inv[dep[x]] % jsb;       if (key < 0) key += jsb;       out1[x] += cnt.ask(key) * v;     }     cnt.clear();     for (int i = (1); i <= (int)q[0]; i++) {       int x = q[i];       int key = (goal - troot[x]) % jsb;       key = key * 1ll * inv[dep[x]] % jsb;       if (key < 0) key += jsb;       cnt.add(key);     }     for (int i = (1); i <= (int)q[0]; i++) {       int x = q[i];       int key = froot[x];       key = (key - val[rt]) % jsb;       if (key < 0) key += jsb;       in1[x] += cnt.ask(key) * v;     }     cnt.clear();     for (int i = (1); i <= (int)q[0]; i++) inq[q[i]] = 0;   }   void fenzhi(int y, int depp) {     int x = getroot(y);     Bfs1(x);     vis[x] = 1;     work(x, x, 1);     for (int i = (0); i <= (int)p[x].size() - 1; i++)       if (!vis[p[x][i]]) work(x, p[x][i], -1);     for (int i = (0); i <= (int)p[x].size() - 1; i++)       if (!vis[p[x][i]]) fenzhi(p[x][i], depp + 1);   }   int main() {     scanf( %d%d%d%d , &n, &jsb, &k, &goal);     powk[0] = 1;     for (int i = (1); i <= (int)n; i++) powk[i] = powk[i - 1] * 1ll * k % jsb;     for (int i = (0); i <= (int)n; i++) inv[i] = Pow(powk[i], jsb - 2);     for (int i = (1); i <= (int)n; i++) scanf( %d , &val[i]);     for (int i = (1); i <= (int)n - 1; i++) {       int u, v;       scanf( %d%d , &u, &v);       p[u].push_back(v);       p[v].push_back(u);     }     fenzhi(1, 0);     long long ans = 0;     for (int i = (1); i <= (int)n; i++) {       in0[i] = n - in1[i];       out0[i] = n - out1[i];       ans = (ans + 2ll * out1[i] * out0[i]);       ans = (ans + 2ll * in1[i] * in0[i]);       ans = (ans + 1ll * in1[i] * out0[i]);       ans = (ans + 1ll * in0[i] * out1[i]);     }     long long pa = n * 1ll * n;     pa = pa * 1ll * n;     ans /= 2;     printf( %I64d n , pa - ans);     return 0;   }   