結果

問題 No.2638 Initial fare
ユーザー pitPpitP
提出日時 2024-02-19 21:41:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 644 ms / 2,000 ms
コード長 6,110 bytes
コンパイル時間 4,895 ms
コンパイル使用メモリ 274,272 KB
実行使用メモリ 158,872 KB
最終ジャッジ日時 2024-02-19 21:42:07
合計ジャッジ時間 14,213 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 1 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 391 ms
39,760 KB
testcase_05 AC 424 ms
41,708 KB
testcase_06 AC 2 ms
6,676 KB
testcase_07 AC 427 ms
46,452 KB
testcase_08 AC 354 ms
48,404 KB
testcase_09 AC 370 ms
51,888 KB
testcase_10 AC 404 ms
52,576 KB
testcase_11 AC 2 ms
6,676 KB
testcase_12 AC 419 ms
42,924 KB
testcase_13 AC 347 ms
41,488 KB
testcase_14 AC 436 ms
49,436 KB
testcase_15 AC 364 ms
50,784 KB
testcase_16 AC 2 ms
6,676 KB
testcase_17 AC 385 ms
42,492 KB
testcase_18 AC 336 ms
43,152 KB
testcase_19 AC 438 ms
55,340 KB
testcase_20 AC 394 ms
48,048 KB
testcase_21 AC 453 ms
63,100 KB
testcase_22 AC 1 ms
6,676 KB
testcase_23 AC 606 ms
158,872 KB
testcase_24 AC 593 ms
140,376 KB
testcase_25 AC 2 ms
6,676 KB
testcase_26 AC 623 ms
106,032 KB
testcase_27 AC 644 ms
143,880 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0