結果
問題 | No.2115 Making Forest Easy |
ユーザー | 沙耶花 |
提出日時 | 2022-10-28 22:41:20 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 720 ms / 2,000 ms |
コード長 | 2,719 bytes |
コンパイル時間 | 4,721 ms |
コンパイル使用メモリ | 269,696 KB |
実行使用メモリ | 359,052 KB |
最終ジャッジ日時 | 2023-09-20 05:51:28 |
合計ジャッジ時間 | 27,222 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 720 ms
358,476 KB |
testcase_03 | AC | 462 ms
102,872 KB |
testcase_04 | AC | 648 ms
279,124 KB |
testcase_05 | AC | 523 ms
208,688 KB |
testcase_06 | AC | 708 ms
358,612 KB |
testcase_07 | AC | 466 ms
50,592 KB |
testcase_08 | AC | 707 ms
358,600 KB |
testcase_09 | AC | 424 ms
43,944 KB |
testcase_10 | AC | 707 ms
359,052 KB |
testcase_11 | AC | 438 ms
102,204 KB |
testcase_12 | AC | 425 ms
43,904 KB |
testcase_13 | AC | 394 ms
91,732 KB |
testcase_14 | AC | 424 ms
44,096 KB |
testcase_15 | AC | 463 ms
48,756 KB |
testcase_16 | AC | 442 ms
94,104 KB |
testcase_17 | AC | 45 ms
12,304 KB |
testcase_18 | AC | 122 ms
62,388 KB |
testcase_19 | AC | 381 ms
187,504 KB |
testcase_20 | AC | 385 ms
42,872 KB |
testcase_21 | AC | 50 ms
23,004 KB |
testcase_22 | AC | 93 ms
23,320 KB |
testcase_23 | AC | 514 ms
243,000 KB |
testcase_24 | AC | 439 ms
93,772 KB |
testcase_25 | AC | 259 ms
99,716 KB |
testcase_26 | AC | 424 ms
44,000 KB |
testcase_27 | AC | 234 ms
51,332 KB |
testcase_28 | AC | 463 ms
50,664 KB |
testcase_29 | AC | 82 ms
41,896 KB |
testcase_30 | AC | 467 ms
49,052 KB |
testcase_31 | AC | 642 ms
275,948 KB |
testcase_32 | AC | 701 ms
359,000 KB |
testcase_33 | AC | 700 ms
358,456 KB |
testcase_34 | AC | 54 ms
15,328 KB |
testcase_35 | AC | 164 ms
82,980 KB |
testcase_36 | AC | 699 ms
358,476 KB |
testcase_37 | AC | 223 ms
49,512 KB |
testcase_38 | AC | 123 ms
28,636 KB |
testcase_39 | AC | 292 ms
147,296 KB |
testcase_40 | AC | 461 ms
48,760 KB |
testcase_41 | AC | 423 ms
43,952 KB |
testcase_42 | AC | 436 ms
103,060 KB |
testcase_43 | AC | 213 ms
27,972 KB |
testcase_44 | AC | 125 ms
29,096 KB |
testcase_45 | AC | 349 ms
38,360 KB |
testcase_46 | AC | 442 ms
102,140 KB |
testcase_47 | AC | 189 ms
24,248 KB |
testcase_48 | AC | 633 ms
266,096 KB |
testcase_49 | AC | 649 ms
287,032 KB |
testcase_50 | AC | 273 ms
65,272 KB |
testcase_51 | AC | 178 ms
41,440 KB |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 template <class Ss, Ss (*op0)(Ss, Ss), Ss (*e)(), class Sv, Ss (*op1)(Sv, Ss), class Se, Ss (*op2)(Se, Ss)> struct rerooting{ int n; vector<vector<int>> to; vector<vector<Se>> edge; vector<Ss> subtree,answer; vector<Sv> vertex; rerooting(int _n){ n = _n; to.resize(n); edge.resize(n); subtree.resize(n,e()); answer.resize(n,e()); vertex.resize(n); } rerooting(vector<Sv> v){ n = v.size(); to.resize(n); edge.resize(n); subtree.resize(n,e()); answer.resize(n,e()); vertex = v; } void add_directed_edge(int u,int v,Se x){ to[u].push_back(v); edge[u].push_back(x); } void add_edge(int u,int v,Se x){ add_directed_edge(u,v,x); add_directed_edge(v,u,x); } void solve(){ dfs(0,-1); redfs(0,-1,e()); } void dfs(int cur,int par){ Ss temp = e(); for(int i=0;i<to[cur].size();i++){ int nxt = to[cur][i]; if(nxt==par)continue; dfs(nxt,cur); temp = op0(temp, op2(edge[cur][i], subtree[nxt])); } subtree[cur] = op1(vertex[cur], temp); } void redfs(int cur, int par, Ss ps){ vector<Ss> P(to[cur].size()+1,e()); rep(i,to[cur].size()){ int nxt = to[cur][i]; if(nxt!=par)P[i+1] = op2(edge[cur][i], subtree[nxt]); else P[i+1] = op2(edge[cur][i], ps); } vector<Ss> S(P.rbegin(),P.rend()-1); S.insert(S.begin(),e()); rep(i,to[cur].size()){ P[i+1] = op0(P[i], P[i+1]); S[i+1] = op0(S[i+1], S[i]); } answer[cur] = op1(vertex[cur], P.back()); for(int i=0;i<to[cur].size();i++){ int nxt = to[cur][i]; if(nxt!=par){ redfs(nxt,cur,op1(vertex[cur], op0(P[i],S[to[cur].size()-1-i]))); } } } }; using A = array<mint,1005>; A e(){ A ret; rep(i,1005)ret[i] = 0; ret[0] = 1; return ret; } A op0(A a,A b){ rep(i,1004){ a[i+1] += a[i]; b[i+1] += b[i]; } A ret = e(); ret[0] = 0; rep(i,1005){ if(i==0)ret[i] = a[i]*b[i]; else{ ret[i] += (a[i]-a[i-1]) * (b[i]-b[i-1]); ret[i] += (a[i]-a[i-1]) * b[i-1]; ret[i] += a[i-1] * (b[i]-b[i-1]); } } return ret; } A op1(int a,A b){ rep(i,a){ b[a] += b[i]; b[i] = 0; } return b; } A op2(int a,A b){ mint s = 0; rep(i,1003)s += b[i]; b[0] += s; return b; } int main(){ int n; cin>>n; vector<int> a(n); rep(i,n)cin>>a[i]; rerooting<A,op0,e,int,op1,int,op2> R(a); rep(i,n-1){ int u,v; cin>>u>>v; R.add_edge(u-1,v-1,1); } R.solve(); mint ans = 0; rep(i,n){ rep(j,1003){ ans += R.answer[i][j] * j; } } cout<<ans.val()<<endl; return 0; }