結果
問題 | No.2598 Kadomatsu on Tree |
ユーザー | Navier_Boltzmann |
提出日時 | 2024-01-02 20:18:59 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 454 ms / 2,000 ms |
コード長 | 2,596 bytes |
コンパイル時間 | 6,713 ms |
コンパイル使用メモリ | 326,636 KB |
実行使用メモリ | 41,412 KB |
最終ジャッジ日時 | 2024-02-26 04:41:04 |
合計ジャッジ時間 | 24,910 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 1 ms
6,676 KB |
testcase_04 | AC | 2 ms
6,676 KB |
testcase_05 | AC | 2 ms
6,676 KB |
testcase_06 | AC | 2 ms
6,676 KB |
testcase_07 | AC | 2 ms
6,676 KB |
testcase_08 | AC | 2 ms
6,676 KB |
testcase_09 | AC | 1 ms
6,676 KB |
testcase_10 | AC | 2 ms
6,676 KB |
testcase_11 | AC | 2 ms
6,676 KB |
testcase_12 | AC | 2 ms
6,676 KB |
testcase_13 | AC | 9 ms
6,676 KB |
testcase_14 | AC | 10 ms
6,676 KB |
testcase_15 | AC | 7 ms
6,676 KB |
testcase_16 | AC | 10 ms
6,676 KB |
testcase_17 | AC | 5 ms
6,676 KB |
testcase_18 | AC | 8 ms
6,676 KB |
testcase_19 | AC | 9 ms
6,676 KB |
testcase_20 | AC | 6 ms
6,676 KB |
testcase_21 | AC | 7 ms
6,676 KB |
testcase_22 | AC | 8 ms
6,676 KB |
testcase_23 | AC | 425 ms
39,384 KB |
testcase_24 | AC | 433 ms
40,228 KB |
testcase_25 | AC | 434 ms
40,436 KB |
testcase_26 | AC | 415 ms
39,684 KB |
testcase_27 | AC | 415 ms
39,684 KB |
testcase_28 | AC | 431 ms
40,348 KB |
testcase_29 | AC | 434 ms
40,716 KB |
testcase_30 | AC | 420 ms
39,568 KB |
testcase_31 | AC | 436 ms
40,624 KB |
testcase_32 | AC | 433 ms
40,104 KB |
testcase_33 | AC | 444 ms
41,056 KB |
testcase_34 | AC | 420 ms
39,064 KB |
testcase_35 | AC | 445 ms
41,380 KB |
testcase_36 | AC | 454 ms
41,072 KB |
testcase_37 | AC | 445 ms
41,084 KB |
testcase_38 | AC | 445 ms
41,408 KB |
testcase_39 | AC | 453 ms
41,412 KB |
testcase_40 | AC | 447 ms
41,408 KB |
testcase_41 | AC | 442 ms
41,412 KB |
testcase_42 | AC | 453 ms
41,412 KB |
testcase_43 | AC | 449 ms
41,412 KB |
testcase_44 | AC | 452 ms
41,408 KB |
testcase_45 | AC | 452 ms
41,412 KB |
testcase_46 | AC | 450 ms
41,408 KB |
testcase_47 | AC | 449 ms
41,412 KB |
testcase_48 | AC | 427 ms
37,204 KB |
testcase_49 | AC | 33 ms
6,676 KB |
testcase_50 | AC | 265 ms
25,612 KB |
testcase_51 | AC | 67 ms
9,748 KB |
testcase_52 | AC | 116 ms
14,128 KB |
testcase_53 | AC | 152 ms
20,324 KB |
testcase_54 | AC | 126 ms
17,576 KB |
testcase_55 | AC | 48 ms
8,960 KB |
testcase_56 | AC | 231 ms
28,856 KB |
testcase_57 | AC | 83 ms
13,104 KB |
testcase_58 | AC | 419 ms
39,788 KB |
testcase_59 | AC | 431 ms
40,632 KB |
testcase_60 | AC | 373 ms
38,012 KB |
testcase_61 | AC | 394 ms
39,836 KB |
testcase_62 | AC | 401 ms
38,468 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep(i,m,n,k) for (int i = (int)(m); i < (int)(n); i += (int)(k)) #define rrep(i,m,n,k) for (int i = (int)(m); i > (int)(n); i += (int)(k)) #define ll long long #define list(T,A,N) vector<T> A(N);for(int i=0;i<(int)(N);i++){cin >> A[i];} using mint = modint998244353; tuple<vector<long long>,vector<long long>, vector<long long>> sub_par_dist(vector<vector<long long >> e, long long root){ long long N = e.size(); vector<long long> par(N,-1); vector<long long> sub(N,-1); vector<long long> dist(N,-1); queue<long long> v; dist[root] = 0; v.push(root); long long x; while (!v.empty()){ x = v.front();v.pop(); for (auto ix:e[x]){ if (dist[ix]!=-1) continue; dist[ix] = dist[x] + 1; v.push(ix); } } vector<pair<long long,long long>> H; for (long long i=0;i<N;i++){ H.push_back({-dist[i],i}); } sort(H.begin(),H.end()); long long tmp; for (auto [h,i]: H){ tmp = 1; for (auto ix:e[i]){ if (sub[ix]==-1){ par[i] = ix; } else{ tmp += sub[ix]; } } sub[i] = tmp; } return {sub,par,dist}; } int main(){ ll N; cin >> N; vector<vector<ll>> e(N); ll u,v; rep(_,0,N-1,1){ cin >> u >> v; u -= 1; v -= 1; e[u].push_back(v); e[v].push_back(u); } list(ll,A,N); auto [sub,par,dist] = sub_par_dist(e,0); mint ans = 0; mint sx,sx2,sy,sy2; rep(i,0,N,1){ sx = mint(0); sy = mint(0); sx2 = mint(0); sy2 = mint(0); for(ll ix:e[i]){ if(par[i]==ix){ if(A[ix]>A[i]){ sx += mint(N-sub[i]); sx2 += mint((N-sub[i])*(N-sub[i])); } else if(A[ix]<A[i]){ sy += mint(N-sub[i]); sy2 += mint((N-sub[i])*(N-sub[i])); } } else{ if(A[ix]>A[i]){ sx += mint(sub[ix]); sx2 += mint(sub[ix]*sub[ix]); } else if(A[ix]<A[i]){ sy += mint(sub[ix]); sy2 += mint(sub[ix]*sub[ix]); } } } ans += (sx*sx - sx2)/mint(2); ans += (sy*sy - sy2)/mint(2); } cout << ans.val() << endl; return 0; }