結果

問題 No.1817 Reversed Edges
コンテスト
ユーザー nrvft
提出日時 2022-01-22 03:49:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 6,299 bytes
コンパイル時間 2,489 ms
コンパイル使用メモリ 212,264 KB
最終ジャッジ日時 2025-01-27 14:44:05
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T1, class T2> inline bool chmax(T1 &a, const T2 &b) {if (a<b) { a=b; return 1;} return 0;}
template<class T1, class T2> inline bool chmin(T1 &a, const T2 &b) {if (b<a) { a=b; return 1;} return 0;}
struct init{init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);cerr<<fixed<<setprecision(15);}}init_;

#ifdef DEBUG
template <class T> void verr(const set<T> &st) { repa(a, st) cerr << a << " "; cerr << endl; }
template <class S, class T> void verr(const map<S, T> &mp) { repa(a, mp) cerr << "{" << a.first << ", " << a.second << "} "; cerr << endl; }
template <class S, class T, class N> void verr(const vector<pair<S,T>>& a, const N& n) { rep(i, n) cerr << "{" << a[i].first << ", " << a[i].second << "} "; cerr << endl; }
template <class T, class N> void verr(const vector<T>& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << endl; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << endl; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
// const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

template<
    class V,
    class E
>
struct ReRooting{
   private:
    struct edge{
        ll to;
        E val;
        ll rev; // G[to]におけるfromのindex
        edge(){}
        edge(ll t_, E v_, ll r_): to(t_), val(v_), rev(r_){}
    };
    ll N;
    vector<vector<edge>> G;         // グラフ
    vector<V> res;                  // 各頂点を根としたときの値
    vector<vector<V>> dp;
    vector<vector<int>> dpused;
    vector<int> resused;

    V vid;
    E eid;

    vector<V> vVals, Vids;

  public:
    ReRooting(ll N_, V vid_, E eid_)
        : N(N_), G(N_), res(N_, vid_), resused(N_), dp(N_), dpused(N_), vid(vid_), eid(eid_) {}

    void add_edge(ll a, ll b, E c){
        G[a].emplace_back(b, c, G[b].size());
        G[b].emplace_back(a, c, G[a].size() - 1);
    }

    // 頂点iのDataを取得
    V get(ll i){
        return res[i];
    }

    V dfs(ll now, ll paridx, bool flag){
        if (paridx != -1 and dpused[now][paridx])
            return dp[now][paridx];
        else if (paridx == -1 and resused[now])
            return res[now];

        // nowが全体の根、または初めの木DPのとき
        if (paridx == -1 or flag) {
            vector<V> A;
            for (ll i = 0; i < G[now].size(); i++) {
                if (i == paridx) continue;
                A.emplace_back(rooting(dfs(G[now][i].to, G[now][i].rev, flag), G[now][i].val));
            }

            // 右からの部分木の累積値
            vector<V> R = vector<V>(A.size() + 1, Vids[now]);
            for (ll i = A.size(); i > 0; i--) R[i - 1] = accumul(R[i], A[i - 1]);

            if (paridx == -1) {
                V L = Vids[now];
                for (ll i = 0; i < G[now].size(); i++) {
                    dpused[now][i] = true;
                    dp[now][i] = apply(merge(L, R[i + 1]), vVals[now]);  //now->to方向の部分木を除いた値
                    // 左から部分木を累積
                    L = accumul(L, A[i]);
                }
            }

            if (paridx == -1) {
                resused[now] = true;
                return res[now] = apply_root(R[0], vVals[now]);
            } else {
                dpused[now][paridx] = true;
                return dp[now][paridx] = apply(R[0], vVals[now]);
            }
        }
        // 2回目のdfsで各頂点を根とするとき
        else {
            dfs(now, -1, flag);
            return dfs(now, paridx, flag);
        }
    }

    void build(vector<V> vvals, vector<V> vids){
        vVals = vvals, Vids = vids;
        for (int i = 0; i < N; i++) dpused[i].resize(G[i].size(), false), dp[i].resize(G[i].size());

        dfs(0, -1, true);

        for (ll i = 0; i < N; i++) dfs(i, -1, false);
    }
};

// 頂点の型
struct vData {
    ll v, size, index;
    // size: 部分木の大きさ
};
// 頂点データの単位元
vData vid = {0, 0, 0};

// 辺の型
struct eData {
    ll v1, v2;
};
// 辺データの単位元
eData eid = {0, 0};

// 累積値に部分木情報を追加
vData accumul(vData acc, vData b){
    acc.v += b.v, acc.size += b.size;
    return acc;
};

// 左からの部分木の累積と右からの累積をマージ
vData merge(vData a, vData b){
    a.v += b.v, a.size += b.size;
    return a;
}

// 1つの部分木情報に辺を適用
vData rooting(vData a, eData e){
    if(a.index == e.v1) {
        // err("eq", a.index, e.v2);
        if(a.index < e.v2) a.v++;
    }else{
        // err("nt", a.index, e.v1);
        if (a.index < e.v1) a.v++;
    }
    // a.v += e.v;
    return a;
}

// マージし終えた頂点で計算
// 1. 根について全ての部分木をマージした後, 各頂点のデータを適用
vData apply_root(vData a, vData f){
    a.size++;
    return a; // ここで部分木のサイズは増える
}
// 2. 根ではない頂点について1つの部分木を除いてマージした後　の2通りに適用
vData apply(vData a, vData f){
    a.size++;
    return a; // ここで部分木のサイズは増える
}

// ReRooting R(N, vid, eid);
// G.build(D); // D: vector<vData> 頂点ごとのデータ
// G.get(i) // 頂点iのvDataを取得


int main() {
    ll N;
    cin >> N;
    ReRooting R(N, vid, eid);
    rep(i, N - 1) {
        ll a, b;
        cin >> a >> b, a--, b--;
        R.add_edge(a, b, {a, b});
    }

    vc<vData> ds(N, vid);
    rep(i, N) ds[i] = {0, 0, i};

    R.build(vc<vData>(N, vid), ds);

    rep(i, N) cout << R.get(i).v << '\n';
}
0