結果

問題 No.2115 Making Forest Easy
ユーザー rickythetarickytheta
提出日時 2022-12-29 14:19:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 699 ms / 2,000 ms
コード長 4,554 bytes
コンパイル時間 1,956 ms
コンパイル使用メモリ 206,660 KB
実行使用メモリ 7,880 KB
最終ジャッジ日時 2024-11-24 16:05:32
合計ジャッジ時間 18,674 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 3 ms
6,852 KB
testcase_02 AC 436 ms
7,084 KB
testcase_03 AC 298 ms
6,932 KB
testcase_04 AC 464 ms
7,196 KB
testcase_05 AC 356 ms
6,984 KB
testcase_06 AC 429 ms
7,488 KB
testcase_07 AC 681 ms
7,368 KB
testcase_08 AC 432 ms
7,236 KB
testcase_09 AC 388 ms
6,852 KB
testcase_10 AC 436 ms
7,096 KB
testcase_11 AC 297 ms
7,880 KB
testcase_12 AC 388 ms
6,856 KB
testcase_13 AC 234 ms
6,872 KB
testcase_14 AC 388 ms
6,892 KB
testcase_15 AC 688 ms
6,900 KB
testcase_16 AC 302 ms
7,364 KB
testcase_17 AC 6 ms
6,820 KB
testcase_18 AC 15 ms
6,820 KB
testcase_19 AC 128 ms
6,928 KB
testcase_20 AC 467 ms
6,888 KB
testcase_21 AC 6 ms
6,820 KB
testcase_22 AC 15 ms
6,816 KB
testcase_23 AC 251 ms
7,132 KB
testcase_24 AC 298 ms
6,852 KB
testcase_25 AC 86 ms
6,816 KB
testcase_26 AC 386 ms
6,952 KB
testcase_27 AC 88 ms
6,816 KB
testcase_28 AC 699 ms
6,816 KB
testcase_29 AC 8 ms
6,980 KB
testcase_30 AC 688 ms
6,820 KB
testcase_31 AC 462 ms
7,072 KB
testcase_32 AC 432 ms
7,620 KB
testcase_33 AC 430 ms
7,324 KB
testcase_34 AC 7 ms
6,820 KB
testcase_35 AC 23 ms
6,820 KB
testcase_36 AC 429 ms
7,140 KB
testcase_37 AC 78 ms
6,824 KB
testcase_38 AC 25 ms
6,816 KB
testcase_39 AC 76 ms
7,236 KB
testcase_40 AC 696 ms
6,868 KB
testcase_41 AC 382 ms
6,912 KB
testcase_42 AC 297 ms
6,900 KB
testcase_43 AC 130 ms
6,824 KB
testcase_44 AC 24 ms
6,820 KB
testcase_45 AC 375 ms
6,964 KB
testcase_46 AC 301 ms
6,892 KB
testcase_47 AC 105 ms
6,832 KB
testcase_48 AC 465 ms
7,152 KB
testcase_49 AC 462 ms
7,052 KB
testcase_50 AC 118 ms
6,820 KB
testcase_51 AC 51 ms
6,820 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