結果
問題 | No.2638 Initial fare |
ユーザー | pitP |
提出日時 | 2024-02-19 21:41:49 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 699 ms / 2,000 ms |
コード長 | 6,110 bytes |
コンパイル時間 | 4,790 ms |
コンパイル使用メモリ | 274,640 KB |
実行使用メモリ | 158,724 KB |
最終ジャッジ日時 | 2024-09-29 01:37:06 |
合計ジャッジ時間 | 15,307 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); } istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); } istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; } ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } typedef long long ll; typedef vector<vector<int>> Graph; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define FOR(i,l,r) for (int i = l;i < (int)(r); i++) #define rep(i,n) for (int i = 0;i < (int)(n); i++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define my_sort(x) sort(x.begin(), x.end()) #define my_max(x) *max_element(all(x)) #define my_min(x) *min_element(all(x)) template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int INF = (1<<30) - 1; const ll LINF = (1LL<<62) - 1; const int MOD = 998244353; const int MOD2 = 1e9+7; const double PI = acos(-1); vector<int> di = {1,0,-1,0}; vector<int> dj = {0,1,0,-1}; #ifdef LOCAL # include <debug_print.hpp> # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast<void>(0)) #endif template <class E, class V, E (*merge)(E, E), E (*e)(), E (*put_edge)(V, int), V (*put_vertex)(E, int)> struct RerootingDP { struct edge { int to, idx, xdi; }; RerootingDP(int n_ = 0) : n(n_), inner_edge_id(0) { es.resize(2*n-2); start.resize(2*n-2); if (n == 1) es_build(); } void add_edge(int u, int v, int idx, int xdi){ start[inner_edge_id] = u; es[inner_edge_id] = {v,idx,xdi}; inner_edge_id++; start[inner_edge_id] = v; es[inner_edge_id] = {u,xdi,idx}; inner_edge_id++; if (inner_edge_id == 2*n-2){ es_build(); } } vector<V> build(int root_ = 0){ root = root_; vector<V> subdp(n); subdp[0] = put_vertex(e(),0); outs.resize(n); vector<int> geta(n+1,0); for (int i = 0; i < n; i++) geta[i+1] = start[i+1] - start[i] - 1; geta[root+1]++; for (int i = 0; i < n; i++) geta[i+1] += geta[i]; auto dfs = [&](auto sfs, int v, int f) -> void { E val = e(); for (int i = start[v]; i < start[v+1]; i++){ if (es[i].to == f){ swap(es[start[v+1]-1],es[i]); } if (es[i].to == f) continue; sfs(sfs,es[i].to,v); E nval = put_edge(subdp[es[i].to],es[i].idx); outs[geta[v]++] = nval; val = merge(val,nval); } subdp[v] = put_vertex(val, v); }; dfs(dfs,root,-1); return subdp; } vector<V> reroot(){ vector<E> reverse_edge(n); reverse_edge[root] = e(); vector<V> answers(n); auto dfs = [&](auto sfs, int v) -> void { int le = outs_start(v); int ri = outs_start(v+1); int siz = ri - le; vector<E> rui(siz+1); rui[siz] = e(); for (int i = siz-1; i >= 0; i--){ rui[i] = merge(outs[le+i],rui[i+1]); } answers[v] = put_vertex(merge(rui[0],reverse_edge[v]),v); E lui = e(); for (int i = 0; i < siz; i++){ V rdp = put_vertex(merge(merge(lui,rui[i+1]),reverse_edge[v]),v); reverse_edge[es[start[v]+i].to] = put_edge(rdp,es[start[v]+i].xdi); lui = merge(lui,outs[le+i]); sfs(sfs,es[start[v]+i].to); } }; dfs(dfs,root); return answers; } private: int n, root, inner_edge_id; vector<E> outs; vector<edge> es; vector<int> start; int outs_start(int v){ int res = start[v] - v; if (root < v) res++; return res; } void es_build(){ vector<edge> nes(2*n-2); vector<int> nstart(n+2,0); for (int i = 0; i < 2*n-2; i++) nstart[start[i]+2]++; for (int i = 0; i < n; i++) nstart[i+1] += nstart[i]; for (int i = 0; i < 2*n-2; i++) nes[nstart[start[i]+1]++] = es[i]; swap(es,nes); swap(start,nstart); } }; using T_monoid = vector<int>; // (ans); using T_DP = vector<int>; // (ans); // T_monoid e(){ return vector<int>{0, 0, 0, 0}; } T_monoid merge(T_monoid a, T_monoid b){ vector<int> res(4); rep(i,4) res[i] = a[i] + b[i]; return res; } T_monoid put_edge(T_DP x, int i){ return x; } T_DP put_vertex(T_monoid x, int v){ x[3] = x[2]; x[2] = x[1]; x[1] = x[0]; x[0] = 1; return x; } int main(){ cin.tie(0); ios_base::sync_with_stdio(false); int N; cin >> N; RerootingDP<T_monoid,T_DP,merge,e,put_edge,put_vertex> g(N); rep(i,N-1){ int u, v; cin >> u >> v; u--; v--; g.add_edge(u,v,i,i); } g.build(); vector<T_DP> ans = g.reroot(); ll cnt = 0; rep(i,N)FOR(d,1,4)cnt+=ans[i][d]; cout << (cnt / 2) << endl; // function<vector<int>(int,int)> dfs = [&](int now, int par){ // vector<int> dp = {0, 0, 0, 0}; // for(int nxt : g[now]){ // if(nxt == par) continue; // vector<int> res = dfs(nxt, now); // dp[0] += res[0]; // dp[1] += res[1]; // dp[2] += res[2]; // } // dp[3] = dp[2]; // dp[2] = dp[1]; // dp[1] = dp[0]; // dp[0] = 1; // return dp; // }; // ll ans = 0; // rep(i,N){ // vector<int> dp = dfs(i, -1); // ans += dp[1] + dp[2] + dp[3]; // } // cout << (ans / 2) << endl; }