結果

問題 No.2115 Making Forest Easy
ユーザー rickythetarickytheta
提出日時 2022-12-29 14:19:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 752 ms / 2,000 ms
コード長 4,554 bytes
コンパイル時間 2,035 ms
コンパイル使用メモリ 198,340 KB
最終ジャッジ日時 2025-02-09 21:44:48
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 50
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:126:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  126 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
main.cpp:127:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  127 |     REP(i,N) scanf("%d", A+i);
      |              ~~~~~^~~~~~~~~~~
main.cpp:130:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  130 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

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