Submission #73603029

---

Source Code Expand

// code template is in https://github.com/drken1215/algorithm/blob/master/template_atcoder.cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;


//------------------------------//
// Utility
//------------------------------//

using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tint = array<int, 3>;
using tll = array<long long, 3>;
using fint = array<int, 4>;
using fll = array<long long, 4>;
using qint = array<int, 5>;
using qll = array<long long, 5>;
using sint = array<int, 6>;
using sll = array<long long, 6>;
using vint = vector<int>;
using vll = vector<long long>;
using dint = deque<int>;
using dll = deque<long long>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vpint = vector<pair<int, int>>;
using vpll = vector<pair<long long, long long>>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
template<class S, class T> inline auto maxll(S a, T b) { return max(ll(a), ll(b)); }
template<class S, class T> inline auto minll(S a, T b) { return min(ll(a), ll(b)); }
template<class T> auto max(const T &a) { return *max_element(a.begin(), a.end()); }
template<class T> auto min(const T &a) { return *min_element(a.begin(), a.end()); }
template<class T> auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto argmin(const T &a) { return *min_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto accum(const vector<T> &a) { return accumulate(a.begin(), a.end(), T()); }
template<class T> auto accum(const deque<T> &a) { return accumulate(a.begin(), a.end(), T()); }

#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl


//------------------------------//
// Graph
//------------------------------//

// Edge Class
template<class T = long long> struct Edge {
    int from, to;
    T val;
    Edge() : from(-1), to(-1) { }
    Edge(int f, int t, T v = 1) : from(f), to(t), val(v) {}
    friend ostream& operator << (ostream& s, const Edge& e) {
        return s << e.from << "->" << e.to << "(" << e.val << ")";
    }
};

// graph class
template<class T = long long> struct Graph {
    vector<vector<Edge<T>>> list;
    vector<vector<Edge<T>>> reversed_list;
    
    Graph(int n = 0) : list(n), reversed_list(n) { }
    void init(int n = 0) {
        list.assign(n, vector<Edge<T>>());
        reversed_list.assign(n, vector<Edge<T>>());
    }
    Graph &operator = (const Graph &g) {
        list = g.list, reversed_list = g.reversed_list;
        return *this;
    }
    const vector<Edge<T>> &operator [] (int i) const { return list[i]; }
    const vector<Edge<T>> &get_rev_edges(int i) const { return reversed_list[i]; }
    const size_t size() const { return list.size(); }
    const void clear() { list.clear(); }
    const void resize(int n) { list.resize(n); }
        
    void add_edge(int from, int to, T val = 1) {
        list[from].push_back(Edge(from, to, val));
        reversed_list[to].push_back(Edge(to, from, val));
    }
    
    void add_bidirected_edge(int from, int to, T val = 1) {
        list[from].push_back(Edge(from, to, val));
        list[to].push_back(Edge(to, from, val));
        reversed_list[from].push_back(Edge(from, to, val));
        reversed_list[to].push_back(Edge(to, from, val));
    }

    friend ostream &operator << (ostream &s, const Graph &G) {
        s << endl;
        for (int i = 0; i < G.size(); ++i) {
            s << i << " -> ";
            for (const auto &e : G[i]) s << e.to << " ";
            s << endl;
        }
        return s;
    }
};
    
// re-rooting
/*
    通常の木 DP において、頂点 v を根とする部分根付き木に関する再帰関数 rec(v) について、
 　　　1. res = IDENTITY
 　　　2. 頂点 v の各子頂点 v2 (その辺を e とする) に対して：res = MERGE(res, rec(v2))
    　　（辺重みあり：res = MERGE(res, ADDEDGE(e, rec(v2)))
 　　　3. return ADDNODE(v, res)
 　　というような更新を行うものとする。
 　　このような木 DP を全方位木 DP へと拡張する。
 */
template<class Monoid, class Weight = long long> struct ReRooting {
    using MergeFunc = function<Monoid(Monoid, Monoid)>;
    using AddNodeFunc = function<Monoid(int, Monoid)>;
    
    // core member
    Graph<Weight> G;  // input graph
    Monoid IDENTITY;
    MergeFunc MERGE;
    AddNodeFunc ADDNODE;
    
    // inner data
    vector<vector<Monoid>> dp;
    vector<unordered_map<int,int>> ids;
    
    // constructor
    ReRooting() {}
    ReRooting(const Graph<Weight> &g,
              const MergeFunc &merge, const AddNodeFunc &addnode, 
              const Monoid &identity) {
        G = g;
        IDENTITY = identity;
        MERGE = merge;
        ADDNODE = addnode;
        build();
    }
    
    // re-looting dp
    Monoid rec(int v, int p) {
        Monoid res = IDENTITY;
        dp[v].assign(G[v].size(), IDENTITY);
        for (int i = 0; i < G[v].size(); ++i) {
            int v2 = G[v][i].to;
            ids[v][v2] = i;
            if (v2 == p) continue;
            dp[v][i] = rec(v2, v);
            res = MERGE(res, dp[v][i]);
        }
        return ADDNODE(v, res);
    }
    void rerec(int v, int p, Monoid pval) {
        for (int i = 0; i < G[v].size(); ++i) {
            int v2 = G[v][i].to;
            if (v2 == p) {
                dp[v][i] = pval;
                continue;
            }
        }
        vector<Monoid> left(G[v].size() + 1, IDENTITY);
        vector<Monoid> right(G[v].size() + 1, IDENTITY);
        for (int i = 0; i < G[v].size(); ++i) {
            left[i + 1] = MERGE(left[i], dp[v][i]);
            right[i + 1] = MERGE(right[i], dp[v][(int)G[v].size() - i - 1]);
        }
        for (int i = 0; i < G[v].size(); ++i) {
            int v2 = G[v][i].to;
            if (v2 == p) continue;
            Monoid pval2 = MERGE(left[i], right[(int)G[v].size() - i - 1]);
            rerec(v2, v, ADDNODE(v, pval2));
        }
    }
    void build() {
        dp.assign(G.size(), vector<Monoid>());
        ids.assign(G.size(), unordered_map<int,int>());
        int root = 0, nullparent = -1;
        rec(root, nullparent);
        rerec(root, nullparent, IDENTITY);
    }
    
    // getter
    Monoid get(int v) {
        Monoid res = IDENTITY;
        for (int i = 0; i < G[v].size(); ++i) {
            res = MERGE(res, dp[v][i]);
        }
        return ADDNODE(v, res);
    }
    Monoid get(int v, int w) {
        return dp[v][ids[v][w]];
    }
    
    // dump
    friend constexpr ostream& operator << (ostream &os, const ReRooting &rr) {
        for (int v = 0; v < rr.G.size(); ++v) {
            for (int i = 0; i < rr.G[v].size(); ++i) {
                os << rr.G[v][i] << ": " << rr.dp[v][i] << endl;
            }
        }
        return os;
    }
};

//------------------------------//
// Solver
//------------------------------//

int main() {
    ll N;
    cin >> N;
    Graph<ll> G(N);
    REP(i, N-1) {
        ll u, v; cin >> u >> v, u--, v--;
        G.add_bidirected_edge(u, v);
    }

    // 左の葉から Greedy で、根の色がどうなるか？
    const ll WHITE = 1, BLACK = 0;
    auto op = [&](ll a, ll b) -> ll { return (a | b); };
    auto addnode = [&](ll v, ll a) -> ll { return 1 - a; };
    ReRooting<ll> rr(G, op, addnode, 0);
    ll res = 0;
    REP(v, N) res += rr.get(v);
    cout << res << endl;
}

Submission Info

Compile Error

./Main.cpp:94:5: warning: type qualifiers ignored on function return type [-Wignored-qualifiers]
   94 |     const size_t size() const { return list.size(); }
      |     ^~~~~
./Main.cpp:95:5: warning: type qualifiers ignored on function return type [-Wignored-qualifiers]
   95 |     const void clear() { list.clear(); }
      |     ^~~~~
./Main.cpp:96:5: warning: type qualifiers ignored on function return type [-Wignored-qualifiers]
   96 |     const void resize(int n) { list.resize(n); }
      |     ^~~~~
./Main.cpp: In lambda function:
./Main.cpp:238:27: warning: unused parameter 'v' [-Wunused-parameter]
  238 |     auto addnode = [&](ll v, ll a) -> ll { return 1 - a; };
      |                        ~~~^
./Main.cpp: In function 'int main()':
./Main.cpp:236:14: warning: unused variable 'WHITE' [-Wunused-variable]
  236 |     const ll WHITE = 1, BLACK = 0;
      |              ^~~~~
./Main.cpp:236:25: warning: unused variable 'BLACK' [-Wunused-variable]
  236 |     const ll WHITE = 1, BLACK = 0;
      |                         ^~~~~
./Main.cpp: In instantiation of 'Monoid ReRooting<Monoid, Weight>::get(int) [with Monoid = long long int; Weight = long long int]':
./Main.cpp:241:28:   required from here
  241 |     REP(v, N) res += rr.get(v);
      |                      ~~~~~~^~~
./Main.cpp:202:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge<long long int>, std::allocator<Edge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |         for (int i = 0; i < G[v].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
./Main.cpp: In instantiation of 'Monoid ReRooting<Monoid, Weight>::rec(int, int) [with Monoid = long long int; Weight = long long int]':
./Main.cpp:195:9:   required from 'void ReRooting<Monoid, Weight>::build() [with Monoid = long long int; Weight = long long int]'
  195 |         rec(root, nullparent);
      |         ^~~
./Main.cpp:154:9:   required from 'ReRooting<Monoid, Weight>::ReRooting(const Graph<Weight>&, const MergeFunc&, const AddNodeFunc&, const Monoid&) [with Monoid = long long int; Weight = long long int; MergeFunc = std::function<long long int(long long int, long long int)>; AddNodeFunc = std::function<long long int(int, long long int)>]'
  154 |         build();
      |         ^~~~~
./Main.cpp:239:39:   required from here
  239 |     ReRooting<ll> rr(G, op, addnode, 0);
      |                                       ^
./Main.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge<long long int>, std::allocator<Edge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         for (int i = 0; i < G[v].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
./Main.cpp: In instantiation of 'void ReRooting<Monoid, Weight>::rerec(int, int, Monoid) [with Monoid = long long int; Weight = long long int]':
./Main.cpp:196:9:   required from 'void ReRooting<Monoid, Weight>::build() [with Monoid = long long int; Weight = long long int]'
  196 |         rerec(root, nullparent, IDENTITY);
      |         ^~~~~
./Main.cpp:154:9:   required from 'ReRooting<Monoid, Weight>::ReRooting(const Graph<Weight>&, const MergeFunc&, const AddNodeFunc&, const Monoid&) [with Monoid = long long int; Weight = long long int; MergeFunc = std::function<long long int(long long int, long long int)>; AddNodeFunc = std::function<long long int(int, long long int)>]'
  154 |         build();
      |         ^~~~~
./Main.cpp:239:39:   required from here
  239 |     ReRooting<ll> rr(G, op, addnode, 0);
      |                                       ^
./Main.cpp:171:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge<long long int>, std::allocator<Edge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |         for (int i = 0; i < G[v].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
./Main.cpp:180:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge<long long int>, std::allocator<Edge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         for (int i = 0; i < G[v].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
./Main.cpp:184:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge<long long int>, std::allocator<Edge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |         for (int i = 0; i < G[v].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~

Judge Result