結果
| 問題 |
No.2116 Making Forest Hard
|
| コンテスト | |
| ユーザー |
 rickytheta
|
| 提出日時 | 2022-12-29 14:20:59 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 4,226 ms / 8,000 ms |
| コード長 | 11,106 bytes |
| コンパイル時間 | 2,259 ms |
| コンパイル使用メモリ | 204,376 KB |
| 最終ジャッジ日時 | 2025-02-09 21:46:03 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 53 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:316:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
316 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
main.cpp:317:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
317 | REP(i,N) scanf("%d", A+i);
| ~~~~~^~~~~~~~~~~
main.cpp:320:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
320 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#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;
}