結果
問題 | No.2949 Product on Tree |
ユーザー |
|
提出日時 | 2024-10-25 22:11:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 231 ms / 2,000 ms |
コード長 | 955 bytes |
コンパイル時間 | 3,537 ms |
コンパイル使用メモリ | 257,168 KB |
実行使用メモリ | 34,700 KB |
最終ジャッジ日時 | 2024-10-25 22:12:18 |
合計ジャッジ時間 | 14,999 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; constexpr int MOD = 998244353; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, l, r) for (int i = (l); i < (int)(r); i++) #define all(v) v.begin(), v.end() ll ans=0; void ch(ll &a,ll b){ a=(a+b)%MOD; } ll dfs(int v,vector<bool>& vst,const vector<vector<int>>& G,const vector<ll>& A){ vst[v]=1; vector c(0,0ll); for(int i:G[v]){ if(!vst[i]){ c.push_back(dfs(i,vst,G,A)); } } ll s=0; for(ll i:c){ ch(ans,s*A[v]%MOD*i); ch(s,i); } ch(ans,s*A[v]); return (s*A[v]+A[v])%MOD; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin>>N; vector A(N,0ll); for(ll &i:A)cin>>i; vector G(N,vector(0,0)); rep(i,N-1){ int U,V; cin>>U>>V; --U,--V; G[U].push_back(V); G[V].push_back(U); } vector vst(N,false); dfs(0,vst,G,A); cout<<ans<<'\n'; }