結果
問題 |
No.364 門松木
|
ユーザー |
![]() |
提出日時 | 2020-02-13 06:37:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 3,000 ms |
コード長 | 1,533 bytes |
コンパイル時間 | 1,266 ms |
コンパイル使用メモリ | 122,456 KB |
実行使用メモリ | 15,616 KB |
最終ジャッジ日時 | 2024-10-05 03:01:59 |
合計ジャッジ時間 | 4,158 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; int n; vector<int> g[50050]; int a[50050]; int c[50050]; void dfs0(int x, int p){ for(auto y:g[x]){ if(y==p) continue; c[y]=-c[x]; dfs0(y, x); } } ll dp[50050]; ll ans; bool used[50050]; void dfs(int x, int p){ used[x]=1; map<int, ll> mp; for(auto y:g[x]){ if(y==p) continue; if(a[y]==a[x] || (c[y]<c[x])!=(a[y]<a[x])) continue; dfs(y, x); mp[a[y]]=max(mp[a[y]], dp[y]); } ll s=0, c=mp.size(); for(auto q:mp){ s+=q.second; } ans=max(ans, s+c*(c-1)/2); if(p==-1) return; s-=mp[a[p]]; c=mp.size(); dp[x]=s+c*(c-1)/2; } int main() { cin>>n; for(int i=0; i<n; i++) cin>>a[i]; for(int i=0; i<n-1; i++){ int x, y; cin>>x>>y; x--; y--; g[x].push_back(y); g[y].push_back(x); } c[0]=1; dfs0(0, -1); for(int i=0; i<n; i++){ if(!used[i]) dfs(i, -1); } for(int i=0; i<n; i++){ c[i]*=(-1), used[i]=0, dp[i]=0; } for(int i=0; i<n; i++){ if(!used[i]) dfs(i, -1); } cout<<ans<<endl; return 0; }