結果
| 問題 |
No.2638 Initial fare
|
| コンテスト | |
| ユーザー |
 pitP
|
| 提出日時 | 2024-02-19 21:41:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 821 ms / 2,000 ms |
| コード長 | 6,110 bytes |
| コンパイル時間 | 4,769 ms |
| コンパイル使用メモリ | 261,620 KB |
| 最終ジャッジ日時 | 2025-02-19 16:46:55 |
|
ジャッジサーバーID （参考情報） |
judge2 / 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;
}