#pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template ostream &operator<<(ostream &os, const vector &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } //////////////////////////////////////////////////////////////////////////////// template struct ModInt { static constexpr unsigned M = M_; unsigned x; constexpr ModInt() : x(0U) {} constexpr ModInt(unsigned x_) : x(x_ % M) {} constexpr ModInt(unsigned long long x_) : x(x_ % M) {} constexpr ModInt(int x_) : x(((x_ %= static_cast(M)) < 0) ? (x_ + static_cast(M)) : x_) {} constexpr ModInt(long long x_) : x(((x_ %= static_cast(M)) < 0) ? (x_ + static_cast(M)) : x_) {} ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; } ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; } ModInt &operator*=(const ModInt &a) { x = (static_cast(x) * a.x) % M; return *this; } ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); } ModInt pow(long long e) const { if (e < 0) return inv().pow(-e); ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b; } ModInt inv() const { unsigned a = M, b = x; int y = 0, z = 1; for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast(q) * z; y = z; z = w; } assert(a == 1U); return ModInt(y); } ModInt operator+() const { return *this; } ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; } ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); } ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); } ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); } ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); } template friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); } template friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); } template friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); } template friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); } explicit operator bool() const { return x; } bool operator==(const ModInt &a) const { return (x == a.x); } bool operator!=(const ModInt &a) const { return (x != a.x); } friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; } }; //////////////////////////////////////////////////////////////////////////////// constexpr unsigned MO = 998244353; using Mint = ModInt; using Pair = pair; Pair operator+(const Pair &a, const Pair &b) { return make_pair(a.first + b.first, a.second + b.second); } Pair operator-(const Pair &a, const Pair &b) { return make_pair(a.first - b.first, a.second - b.second); } Pair operator*(const Pair &a, const Pair &b) { return make_pair(a.first * b.first, a.first * b.second + a.second * b.first); } Pair &operator+=(Pair &a, const Pair &b) { return a = a + b; } Pair &operator-=(Pair &a, const Pair &b) { return a = a - b; } Pair &operator*=(Pair &a, const Pair &b) { return a = a * b; } constexpr Pair ZERO(0, 0); Pair operator*(const Mint &k, const Pair &a) { return make_pair(k * a.first, k * a.second); } struct Node { int l, r; Pair f, g; Pair lz; Node() {} void push(Node &l_, Node &r_) { if (!(lz.first == 1 && lz.second == 0)) { l_.mul(lz); r_.mul(lz); lz.first = 1; lz.second = 0; } } void pull(const Node &l_, const Node &r_) { f = l_.f + r_.f; g = l_.g + r_.g; } void mul(const Pair &val) { f *= val; g *= val; lz *= val; } }; int nodesLen = 1; Node nodes[10'000'010]; int newNode() { const int u = nodesLen++; nodes[u].lz.first = 1; return u; } void rangeMul(int a, int l, int r, int ql, int qr, const Pair &val) { #ifdef LOCAL assert(a); #endif if (qr <= l || r <= ql) { // } else if (ql <= l && r <= qr) { nodes[a].mul(val); } else { const int mid = (l + r) / 2; int &al = nodes[a].l; int &ar = nodes[a].r; if (!al) { al = newNode(); ar = newNode(); } nodes[a].push(nodes[al], nodes[ar]); rangeMul(al, l, mid, ql, qr, val); rangeMul(ar, mid, r, ql, qr, val); nodes[a].pull(nodes[al], nodes[ar]); } } void pointAdd(int a, int l, int r, int q, const Pair &f, const Pair &g) { #ifdef LOCAL assert(a); #endif if (q + 1 <= l || r <= q) { // } else if (q <= l && r <= q + 1) { nodes[a].f += f; nodes[a].g += g; } else { const int mid = (l + r) / 2; int &al = nodes[a].l; int &ar = nodes[a].r; if (!al) { al = newNode(); ar = newNode(); } nodes[a].push(nodes[al], nodes[ar]); pointAdd(al, l, mid, q, f, g); pointAdd(ar, mid, r, q, f, g); nodes[a].pull(nodes[al], nodes[ar]); } } Pair rangeSum(int a, int l, int r, int ql, int qr) { #ifdef LOCAL assert(a); #endif if (qr <= l || r <= ql) { return ZERO; } else if (ql <= l && r <= qr) { return nodes[a].f; } else { const int mid = (l + r) / 2; int &al = nodes[a].l; int &ar = nodes[a].r; if (!al) { al = newNode(); ar = newNode(); } nodes[a].push(nodes[al], nodes[ar]); Pair ret = ZERO; ret += rangeSum(al, l, mid, ql, qr); ret += rangeSum(ar, mid, r, ql, qr); nodes[a].pull(nodes[al], nodes[ar]); return ret; } } int create(int l, int r, int q, const Pair &f, const Pair &g) { if (q + 1 <= l || r <= q) { const int a = newNode(); return a; } else if (q <= l && r <= q + 1) { const int a = newNode(); nodes[a].f = f; nodes[a].g = g; return a; } else { const int mid = (l + r) / 2; const int al = create(l, mid, q, f, g); const int ar = create(mid, r, q, f, g); const int a = newNode(); nodes[a].l = al; nodes[a].r = ar; nodes[a].pull(nodes[al], nodes[ar]); return a; } } constexpr Mint INV2 = (1 + MO) / 2; int N; vector C; vector A, B; vector> graph; int csLen; vector cs; Mint ans; vector> ss; vector rs; void dfs(int u, int p) { for (const int v : graph[u]) if (p != v) { dfs(v, u); } const int pos = lower_bound(cs.begin(), cs.end(), C[u]) - cs.begin(); ss[u].insert(pos); rs[u] = create(0, csLen, pos, Pair(1, 1), Pair(cs[pos], cs[pos])); for (const int v : graph[u]) if (p != v) { ans += INV2 * nodes[rs[v]].g.second; bool sw = false; if (ss[u].size() < ss[v].size()) { sw = true; swap(ss[u], ss[v]); swap(rs[u], rs[v]); } vector xs(ss[v].begin(), ss[v].end()); const int len = xs.size(); xs.push_back(csLen); vector gs(len); // xu < xv vector hs(len); for (int j = 0; j < len; ++j) { gs[j] = INV2 * rangeSum(rs[v], 0, csLen, xs[j], xs[j] + 1); hs[j] = gs[j] * rangeSum(rs[u], 0, csLen, 0, xs[j]); } // cerr<= xv { Pair sum = sw ? ZERO : Pair(INV2, 0); rangeMul(rs[u], 0, csLen, 0, xs[0], sum); for (int j = 0; j < len; ++j) { sum += gs[j]; rangeMul(rs[u], 0, csLen, xs[j], xs[j + 1], sum); } } for (int j = 0; j < len; ++j) { const Pair h = sw ? (gs[j] + hs[j]) : hs[j]; pointAdd(rs[u], 0, csLen, xs[j], h, cs[xs[j]] * h); } for (int j = 0; j < len; ++j) { ss[u].insert(xs[j]); } } // cerr<<"DONE u = "<