結果

問題 No.2116 Making Forest Hard
ユーザー rickythetarickytheta
提出日時 2022-12-29 14:20:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,725 ms / 8,000 ms
コード長 11,106 bytes
コンパイル時間 2,266 ms
コンパイル使用メモリ 211,724 KB
実行使用メモリ 38,504 KB
最終ジャッジ日時 2024-11-24 16:07:09
合計ジャッジ時間 63,597 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
19,440 KB
testcase_01 AC 6 ms
19,308 KB
testcase_02 AC 569 ms
25,960 KB
testcase_03 AC 549 ms
25,836 KB
testcase_04 AC 1,111 ms
32,132 KB
testcase_05 AC 1,342 ms
25,988 KB
testcase_06 AC 3,398 ms
35,820 KB
testcase_07 AC 3,725 ms
34,796 KB
testcase_08 AC 1,807 ms
32,620 KB
testcase_09 AC 2,304 ms
35,184 KB
testcase_10 AC 89 ms
19,948 KB
testcase_11 AC 1,004 ms
24,500 KB
testcase_12 AC 2,939 ms
35,052 KB
testcase_13 AC 1,187 ms
26,220 KB
testcase_14 AC 1,809 ms
25,964 KB
testcase_15 AC 11 ms
19,308 KB
testcase_16 AC 2,904 ms
38,504 KB
testcase_17 AC 690 ms
23,968 KB
testcase_18 AC 387 ms
24,696 KB
testcase_19 AC 886 ms
27,116 KB
testcase_20 AC 1,153 ms
26,216 KB
testcase_21 AC 321 ms
22,256 KB
testcase_22 AC 896 ms
24,936 KB
testcase_23 AC 276 ms
21,484 KB
testcase_24 AC 31 ms
20,076 KB
testcase_25 AC 1,614 ms
28,012 KB
testcase_26 AC 2,797 ms
38,376 KB
testcase_27 AC 82 ms
20,456 KB
testcase_28 AC 265 ms
23,532 KB
testcase_29 AC 894 ms
24,940 KB
testcase_30 AC 363 ms
24,556 KB
testcase_31 AC 269 ms
21,484 KB
testcase_32 AC 1,155 ms
26,224 KB
testcase_33 AC 16 ms
19,436 KB
testcase_34 AC 627 ms
24,172 KB
testcase_35 AC 1,161 ms
26,092 KB
testcase_36 AC 1,772 ms
32,632 KB
testcase_37 AC 71 ms
20,152 KB
testcase_38 AC 2,993 ms
37,996 KB
testcase_39 AC 1,409 ms
26,092 KB
testcase_40 AC 265 ms
21,200 KB
testcase_41 AC 752 ms
23,996 KB
testcase_42 AC 419 ms
24,812 KB
testcase_43 AC 590 ms
25,836 KB
testcase_44 AC 1,288 ms
25,708 KB
testcase_45 AC 506 ms
22,636 KB
testcase_46 AC 579 ms
25,836 KB
testcase_47 AC 662 ms
23,020 KB
testcase_48 AC 301 ms
21,104 KB
testcase_49 AC 8 ms
19,308 KB
testcase_50 AC 1,220 ms
26,092 KB
testcase_51 AC 1,373 ms
25,988 KB
testcase_52 AC 1,381 ms
25,988 KB
testcase_53 AC 1,410 ms
25,988 KB
testcase_54 AC 2,269 ms
25,964 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)
    Data() {
        X = Y = W = mint::raw(1);
    }
    Data(bool is_target) {
        X = Y = mint::raw(is_target);
        W = mint::raw(1);
    }

    void addchild(const Data& child) {
        // merge
        const mint childXW = child.X + child.W;
        Y = Y * childXW + X * child.Y;
        X = X * childXW;
        // add edge
        W *= child.W * mint::raw(2);
    }
};
struct Coeff {
    mint A{mint::raw(1)};
    mint B{mint::raw(0)};
    mint C{mint::raw(0)};
    mint D{mint::raw(0)};
    mint E{mint::raw(1)};

    Coeff(){}
    void leftmuleq(const Data& dp) {
        const mint CE = C + E;
        B = A * dp.Y + B * dp.X;
        A = A * dp.X;
        D = CE * dp.Y + D * dp.X;
        C = CE * dp.X;
        E = E * mint::raw(2u) * dp.W;
    }
    void rightmuleq(const Data& dp) {
        const mint W2 = dp.W + dp.W;
        E = E * W2;
        D = A * dp.Y + B * dp.X + D * W2;
        C = A * dp.X + C * W2;
        B = A * dp.Y + B * dp.X;
        A = A * dp.X;
    }
    Data apply(const Data& rhs) {
        Data ret{};
        ret.X = A * rhs.X             + C * rhs.W;
        ret.Y = B * rhs.X + A * rhs.Y + D * rhs.W;
        ret.W =                         E * rhs.W;
        return ret;
    }
};

// sqrt decomposition + rerooting
struct SqrtRerooting {
    // id, rerooted parent
    int id = -1, par = -1;
    // dp value
    Data dp{};

    // memoized value
    Data dp_static{};
    // memoized coeff
    bool is_compressed = false;
    Coeff compressed_coeff{};

    // topology data
    bool is_dynamic = false;
    int child_dynamic_count = 0;
    int boundary_link = -1;
    vi dynamic_adj;

    bool has_dynamic() const { return is_dynamic || child_dynamic_count > 0; }
    bool is_divider() const { return is_dynamic || child_dynamic_count >= 2; }
};
// sr_root と SR.is_dynamic は外部からセットする
SqrtRerooting SR[125252];
int sr_root = -1;
void sr_compress_dfs(int pos, int bef);
void sr_prepare_dfs(int pos, int bef = -1) {
    SqrtRerooting& cur = SR[pos];
    cur.id = pos;
    cur.par = bef;
    cur.dp = Data{B[pos] <= B[sr_root]};
    cur.dp_static = cur.dp;
    cur.is_compressed = false;
    cur.compressed_coeff = Coeff{};
    cur.child_dynamic_count = 0;
    cur.boundary_link = -1;
    cur.dynamic_adj.clear();
    if (bef != -1) cur.dynamic_adj.push_back(bef);
    int leaf_dynamic_subtree = -1;
    for (int to : g[pos]) if (to != bef) {
        sr_prepare_dfs(to, pos);
        const SqrtRerooting& child = SR[to];

        cur.dp.addchild(child.dp);
        if (child.has_dynamic()) {
            // dynamic subtree
            cur.child_dynamic_count++;
            leaf_dynamic_subtree = to;
            cur.dynamic_adj.push_back(to);
        } else {
            // static subtree
            cur.dp_static.addchild(child.dp);
        }
    }
    if (!cur.is_divider() && cur.child_dynamic_count == 1) {
        const SqrtRerooting& child = SR[leaf_dynamic_subtree];
        if (child.is_divider()) {
            cur.boundary_link = pos;
        } else {
            cur.boundary_link = child.boundary_link;
        }
        cur.compressed_coeff = child.compressed_coeff;
        cur.compressed_coeff.leftmuleq(cur.dp_static);
    }

    if (pos == sr_root) {
        sr_compress_dfs(sr_root, -1);
    }
}
void sr_compress_dfs(int pos, int bef) {
    SqrtRerooting& cur = SR[pos];

    if (!cur.is_divider() && cur.child_dynamic_count == 1) {
        if (cur.boundary_link == pos) {
            // 長さ1なので圧縮しない
        } else if (cur.is_compressed) {
            // 根側から圧縮計算が済んでいる
            cur.compressed_coeff.leftmuleq(cur.dp_static);
        } else {
            cur.is_compressed = true;
            // 葉側にリンク
            SqrtRerooting& leaf_link = SR[cur.boundary_link];
            if (!leaf_link.is_compressed) {
                // curが根側リンクになる
                leaf_link.boundary_link = pos;
                leaf_link.is_compressed = true;
                leaf_link.compressed_coeff = Coeff{};
                leaf_link.par = pos;
            }
            leaf_link.compressed_coeff.leftmuleq(cur.dp_static);
        }
    }
    for (int to : cur.dynamic_adj) if (to != bef) {
        sr_compress_dfs(to, pos);
    }
}
void update(int i) {
    SqrtRerooting& cur = SR[i];
    cur.dp = cur.dp_static;
    for (int to : cur.dynamic_adj) if (to != cur.par) {
        cur.dp.addchild(SR[to].dp);
    }
}
void makerootInner(int i) {
    if (i == sr_root) return;
    SqrtRerooting& cur = SR[i];
    SqrtRerooting& par = SR[cur.par];
    if (par.is_compressed) {
        SqrtRerooting& link = SR[par.boundary_link];
        SqrtRerooting& root = SR[link.par];
        makerootInner(root.id);
        // (-1) <- root <- link <- par <- cur
        //         root -> link -> par -> cur -> (-1)
        root.par = link.id;
        link.par = par.id;
        par.par = cur.id;
        cur.par = -1;
        update(root.id);
        par.dp = par.compressed_coeff.apply(root.dp);
        // cur.update();
    } else {
        makerootInner(par.id);
        // (-1) <- par <- cur
        //         par -> cur -> (-1)
        par.par = cur.id;
        cur.par = -1;
        update(par.id);
        // cur.update();
    }
}
void makeroot(int i) {
    if (i == sr_root) return;
    makerootInner(i);
    sr_root = i;
    update(i);
}
void sr_dump(int pos = -1, int bef = -1, int sh = 2) {
    if (pos == -1) pos = sr_root;
    const SqrtRerooting& cur = SR[pos];
    printf("%*c[%2d%s] ", sh, ' ', pos, cur.is_compressed ? "(C)" : cur.is_dynamic ? "(D)" : cur.is_divider() ? "(D')" : "");
    printf("dp:(%u,%u,%u) ", cur.dp.X.val, cur.dp.Y.val, cur.dp.W.val);
    if (sh > 2 * N) {
        puts("\nerror");
        exit(0);
    }
    if (cur.is_compressed) {
        printf("link:%d ", cur.boundary_link);
        printf("co:(%u,%u,%u,%u,%u)\n", cur.compressed_coeff.A.val, cur.compressed_coeff.B.val, cur.compressed_coeff.C.val, cur.compressed_coeff.D.val, cur.compressed_coeff.E.val);
        for (int to : SR[cur.boundary_link].dynamic_adj) if (SR[to].is_divider()) {
            sr_dump(to, cur.boundary_link, sh+2);
        }
    } else {
        printf("dpS:(%u,%u,%u)\n", cur.dp_static.X.val, cur.dp_static.Y.val, cur.dp_static.W.val);
        for (int to : cur.dynamic_adj) if (to != bef) {
            sr_dump(to, pos, sh+2);
        }
    }
}

// dp calc
Data dfs(int v, int bef, int root) {
    Data dp{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;

    reverse(order, order+N);

    mint ans = 0;
    // sqrt decomposition rerooting
    constexpr int M = 1000;
    int it = 0;
    while(it < N) {
        int it_end = min(it + M, N);
        FOR(i, it, it_end) SR[order[i]].is_dynamic = true;
        sr_root = order[it];
        sr_prepare_dfs(sr_root, -1);
        FOR(i, it, it_end) {
            int id = order[i];
            makeroot(id);
            // sr_dump();
            ans += mint::raw(A[id]) * SR[id].dp.Y;
            SR[id].dp.X = SR[id].dp.Y = mint::raw(0);
            SR[id].dp_static.X = SR[id].dp_static.Y = mint::raw(0);
        }
        FOR(i, it, it_end) SR[order[i]].is_dynamic = false;
        it = it_end;
    }
    printf("%u\n", ans.val);
    return 0;
}
0