結果
問題 | No.2115 Making Forest Easy |
ユーザー | bayashiko |
提出日時 | 2022-10-08 17:50:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 184 ms / 2,000 ms |
コード長 | 3,601 bytes |
コンパイル時間 | 4,898 ms |
コンパイル使用メモリ | 280,144 KB |
実行使用メモリ | 161,408 KB |
最終ジャッジ日時 | 2023-09-04 23:30:10 |
合計ジャッジ時間 | 11,658 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
43,088 KB |
testcase_01 | AC | 26 ms
43,048 KB |
testcase_02 | AC | 174 ms
161,196 KB |
testcase_03 | AC | 90 ms
43,112 KB |
testcase_04 | AC | 153 ms
127,856 KB |
testcase_05 | AC | 125 ms
103,276 KB |
testcase_06 | AC | 174 ms
161,212 KB |
testcase_07 | AC | 97 ms
45,388 KB |
testcase_08 | AC | 174 ms
161,212 KB |
testcase_09 | AC | 93 ms
43,320 KB |
testcase_10 | AC | 179 ms
161,408 KB |
testcase_11 | AC | 91 ms
43,200 KB |
testcase_12 | AC | 93 ms
43,368 KB |
testcase_13 | AC | 84 ms
43,088 KB |
testcase_14 | AC | 92 ms
43,396 KB |
testcase_15 | AC | 97 ms
45,024 KB |
testcase_16 | AC | 92 ms
43,424 KB |
testcase_17 | AC | 32 ms
42,876 KB |
testcase_18 | AC | 50 ms
62,528 KB |
testcase_19 | AC | 106 ms
103,500 KB |
testcase_20 | AC | 85 ms
45,180 KB |
testcase_21 | AC | 36 ms
48,880 KB |
testcase_22 | AC | 39 ms
43,140 KB |
testcase_23 | AC | 129 ms
120,412 KB |
testcase_24 | AC | 91 ms
43,224 KB |
testcase_25 | AC | 75 ms
70,712 KB |
testcase_26 | AC | 93 ms
43,456 KB |
testcase_27 | AC | 61 ms
43,316 KB |
testcase_28 | AC | 98 ms
45,460 KB |
testcase_29 | AC | 43 ms
55,840 KB |
testcase_30 | AC | 97 ms
44,952 KB |
testcase_31 | AC | 152 ms
126,560 KB |
testcase_32 | AC | 184 ms
161,348 KB |
testcase_33 | AC | 175 ms
161,096 KB |
testcase_34 | AC | 34 ms
42,932 KB |
testcase_35 | AC | 61 ms
69,556 KB |
testcase_36 | AC | 175 ms
161,180 KB |
testcase_37 | AC | 59 ms
43,088 KB |
testcase_38 | AC | 44 ms
42,968 KB |
testcase_39 | AC | 86 ms
91,100 KB |
testcase_40 | AC | 97 ms
44,740 KB |
testcase_41 | AC | 92 ms
43,320 KB |
testcase_42 | AC | 91 ms
43,132 KB |
testcase_43 | AC | 59 ms
45,140 KB |
testcase_44 | AC | 44 ms
42,992 KB |
testcase_45 | AC | 80 ms
44,612 KB |
testcase_46 | AC | 91 ms
43,172 KB |
testcase_47 | AC | 54 ms
44,540 KB |
testcase_48 | AC | 149 ms
122,456 KB |
testcase_49 | AC | 154 ms
131,036 KB |
testcase_50 | AC | 66 ms
43,076 KB |
testcase_51 | AC | 53 ms
43,116 KB |
ソースコード
#if defined(LOCAL) #include<stdc++.h> #else #include<bits/stdc++.h> #endif #include<random> #pragma GCC optimize("Ofast") //#pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") using namespace std; //#include<boost/multiprecision/cpp_int.hpp> //#include<boost/multiprecision/cpp_dec_float.hpp> //namespace mp=boost::multiprecision; //#define mulint mp::cpp_int //#define mulfloat mp::cpp_dec_float_100 struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init; //#define INF (1<<30) #define LINF (lint)(1LL<<56) #define MINF (lint)(2e18) #define endl "\n" #define rep(i,n) for(lint (i)=0;(i)<(n);(i)++) #define reprev(i,n) for(lint (i)=(n-1);(i)>=0;(i)--) #define flc(x) __builtin_popcountll(x) #define pint pair<int,int> #define pdouble pair<double,double> #define plint pair<lint,lint> #define fi first #define se second #define all(x) x.begin(),x.end() //#define vec vector<lint> #define nep(x) next_permutation(all(x)) typedef long long lint; int dx[8]={1,1,0,-1,-1,-1,0,1}; int dy[8]={0,1,1,1,0,-1,-1,-1}; const int MAX_N=3e5+5; template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;} //vector<int> bucket[MAX_N/1000]; //constexpr int MOD=1000000007; constexpr int MOD=998244353; #include<atcoder/all> using namespace atcoder; typedef __int128_t llint; using mint=modint998244353; int N; lint A[5005]; vector<int> edge[5005]; mint dp1[5005][1005]; //頂点iを根とする部分木の、最大値がjになる切り方の総和 mint dp2[5005][1005]; //頂点iを根とする部分木の、最大値がjになる切り方のサイズの総和 int dp3[5005]; //部分木のサイズ mint pow2[5005]; void dfs(int now,int par){ for(auto child:edge[now]){ if(child==par) continue; dfs(child,now); //now-childの辺を切る場合、dp_sub[j]-1本の辺は自由になる //サイズ0,max0の切り方が2^(subsize-1)通りあると考える dp1[child][0]=pow2[dp3[child]-1]; dp2[child][0]=0; //切らない場合、mergeする mint merge1[1001],merge2[1001]; mint dp1sum_now[1002],dp2sum_now[1002],dp1sum_child[1002],dp2sum_child[1002]; rep(i,1001){ dp1sum_now[i+1]=dp1sum_now[i]+dp1[now][i]; dp2sum_now[i+1]=dp2sum_now[i]+dp2[now][i]; dp1sum_child[i+1]=dp1sum_child[i]+dp1[child][i]; dp2sum_child[i+1]=dp2sum_child[i]+dp2[child][i]; } rep(i,1001){ merge1[i]+=dp1sum_now[i+1]*dp1sum_child[i+1]; merge2[i]+=dp1sum_now[i+1]*dp2sum_child[i+1]; merge2[i]+=dp1sum_child[i+1]*dp2sum_now[i+1]; } reprev(i,1000){ merge1[i+1]-=merge1[i]; merge2[i+1]-=merge2[i]; } /*rep(i,501) rep(j,501){ merge1[max(i,j)]+=dp1[now][i]*dp1[child][j]; merge2[max(i,j)]+=dp1[now][i]*dp2[child][j]+dp1[child][j]*dp2[now][i]; }*/ rep(j,1001){ dp1[now][j]=merge1[j]; dp2[now][j]=merge2[j]; } dp3[now]+=dp3[child]; } } int main(void){ cin >> N; rep(i,N) cin>> A[i]; rep(i,N-1){ int u,v; cin >> u >> v; u--,v--; edge[u].push_back(v); edge[v].push_back(u); } pow2[0]=1; rep(i,5004) pow2[i+1]=pow2[i]*2; rep(i,N) dp1[i][A[i]]=1,dp2[i][A[i]]=1,dp3[i]=1; dfs(0,-1); mint ans=0; rep(i,N) rep(j,1001) ans+=dp2[i][j]*j*pow2[N-1-dp3[i]+(i==0)]; cout << ans.val() << endl; }