結果

問題 No.2115 Making Forest Easy
ユーザー rickythetarickytheta
提出日時 2022-12-29 14:19:39
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 900 ms / 2,000 ms
コード長 4,554 bytes
コンパイル時間 2,480 ms
コンパイル使用メモリ 205,292 KB
実行使用メモリ 8,004 KB
最終ジャッジ日時 2024-05-03 14:59:38
合計ジャッジ時間 20,964 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,812 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 483 ms
7,240 KB
testcase_03 AC 334 ms
6,944 KB
testcase_04 AC 515 ms
7,176 KB
testcase_05 AC 385 ms
6,964 KB
testcase_06 AC 485 ms
7,748 KB
testcase_07 AC 900 ms
6,944 KB
testcase_08 AC 482 ms
7,240 KB
testcase_09 AC 433 ms
6,940 KB
testcase_10 AC 485 ms
7,084 KB
testcase_11 AC 333 ms
6,944 KB
testcase_12 AC 434 ms
6,944 KB
testcase_13 AC 268 ms
6,940 KB
testcase_14 AC 432 ms
6,944 KB
testcase_15 AC 778 ms
6,940 KB
testcase_16 AC 337 ms
6,940 KB
testcase_17 AC 7 ms
7,240 KB
testcase_18 AC 17 ms
6,940 KB
testcase_19 AC 143 ms
7,236 KB
testcase_20 AC 514 ms
7,492 KB
testcase_21 AC 6 ms
6,944 KB
testcase_22 AC 17 ms
7,748 KB
testcase_23 AC 279 ms
7,132 KB
testcase_24 AC 336 ms
6,944 KB
testcase_25 AC 96 ms
6,944 KB
testcase_26 AC 432 ms
8,004 KB
testcase_27 AC 98 ms
6,940 KB
testcase_28 AC 779 ms
6,940 KB
testcase_29 AC 9 ms
6,940 KB
testcase_30 AC 779 ms
7,240 KB
testcase_31 AC 522 ms
7,160 KB
testcase_32 AC 484 ms
7,208 KB
testcase_33 AC 480 ms
7,328 KB
testcase_34 AC 8 ms
6,944 KB
testcase_35 AC 27 ms
7,084 KB
testcase_36 AC 484 ms
7,092 KB
testcase_37 AC 87 ms
6,944 KB
testcase_38 AC 28 ms
6,940 KB
testcase_39 AC 81 ms
6,944 KB
testcase_40 AC 779 ms
6,940 KB
testcase_41 AC 433 ms
6,944 KB
testcase_42 AC 333 ms
6,940 KB
testcase_43 AC 147 ms
6,940 KB
testcase_44 AC 28 ms
6,940 KB
testcase_45 AC 416 ms
6,940 KB
testcase_46 AC 332 ms
6,944 KB
testcase_47 AC 117 ms
6,940 KB
testcase_48 AC 523 ms
7,616 KB
testcase_49 AC 512 ms
7,220 KB
testcase_50 AC 130 ms
6,940 KB
testcase_51 AC 57 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;

using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
#define ALL(v) (v).begin(),(v).end()

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl

constexpr unsigned MOD = 998'244'353u;

struct mint {
    unsigned val;

    // constructor
    constexpr mint():val(0u){}
    template<typename T, enable_if_t<is_integral_v<T> && is_signed_v<T>, nullptr_t> = nullptr>
    constexpr mint(T v){
        v = v % MOD;
        val = unsigned(v < 0 ? (v + MOD) : v);
    }
    template<typename T, enable_if_t<is_integral_v<T> && is_unsigned_v<T>, nullptr_t> = nullptr>
    constexpr mint(T v):val(unsigned(v % MOD)){}
    // raw
    template<typename T, enable_if_t<is_integral_v<T>, nullptr_t> = nullptr>
    static constexpr mint raw(T v) { mint x; x.val = unsigned(v); return x; }

    // operator
    constexpr mint& operator++() { if (++val == MOD) {val = 0;} return *this; }
    constexpr mint& operator--() { if (val-- == 0u) {val = MOD - 1;} return *this; }
    constexpr mint operator++(int) { mint ret = *this; ++*this; return ret; }
    constexpr mint operator--(int) { mint ret = *this; --*this; return ret; }

    constexpr mint& operator+=(const mint& that) { if ((val += that.val) >= MOD) {val -= MOD;} return *this; }
    constexpr mint& operator-=(const mint& that) { if ((val -= that.val) >= MOD) {val += MOD;} return *this; }
    constexpr mint& operator*=(const mint& that) { val = unsigned(ull(val) * that.val % MOD); return *this; }
    mint& operator/=(const mint& that) { return *this *= that.inv(); }

    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return raw(0) - *this; }

    constexpr mint operator+(const mint& that) const { return mint(*this) += that; }
    constexpr mint operator-(const mint& that) const { return mint(*this) -= that; }
    constexpr mint operator*(const mint& that) const { return mint(*this) *= that; }
    mint operator/(const mint& that) const { return mint(*this) /= that; }

    constexpr bool operator==(const mint& that) const { return val == that.val; }
    constexpr bool operator!=(const mint& that) const { return val != that.val; }

    // function
    mint& poweq(ll x) {     // note: x is not mint
        mint a = *this;
        val = 1u;
        while (x) {
            if (x&1) *this *= a;
            a *= a;
            x >>= 1;
        }
        return *this;
    }
    mint pow(ll x) const { return mint(*this).poweq(x); }

    mint& inveq() { return poweq(MOD - 2); }
    mint inv() const { return pow(MOD - 2); }
};

// input
int N;
int A[125252];
vi g[125252];

// prepare
int order[125252];
int B[125252];

// dp data
struct Data {
    mint X{mint::raw(1)};   // pattern num
    mint Y{mint::raw(1)};   // score sum for all pattern
    mint W{mint::raw(1)};   // pow(2, edge num)
    bool is_target = false;

    void addchild(const Data& child) {
        if (child.is_target) {
            // merge
            const mint childXW = child.X + child.W;
            Y = Y * childXW + X * child.Y;
            X *= childXW;
        } else {
            // cut
            Y *= child.W;
            X *= child.W;
        }
        // add edge
        W *= child.W * mint::raw(2);
    }
};

// dp calc
Data dfs(int v, int bef, int root) {
    Data dp{};
    dp.is_target = B[v] <= B[root];
    for (int to : g[v]) if (to != bef) {
        Data child = dfs(to, v, root);
        dp.addchild(child);
    }
    return dp;
}

int main(){
    // input
    scanf("%d", &N);
    REP(i,N) scanf("%d", A+i);
    REP(i,N-1) {
        int u,v;
        scanf("%d%d", &u, &v);
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // calc order
    iota(order, order+N, 0);
    sort(order, order+N, [](int i, int j){
        if (A[i] != A[j]) { return A[i] < A[j]; }
        return i < j;
    });
    REP(i,N)B[order[i]] = i;
    // calc dp
    mint ans = 0;
    REP(i,N){
        Data dp = dfs(i, -1, i);
        ans += mint::raw(A[i]) * dp.Y;
    }
    printf("%u\n", ans.val);
    return 0;
}
0