Submission #27455889

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;
using std::pair;

class Tree {
    private:
        static const int ROOT = 0;
        const int mod;
        const vector<vector<int>>& neighbors;
        vector<long long> paint_ways;
        vector<long long> parent_ways;
        vector<long long> other_subtrees;

        /*
         * first find the number of painting ways for each node
         * given that we only consider the stuff in its subtree
         */
        void subtree_paint(int at, int prev) {
            for (int n : neighbors[at]) {
                if (n != prev) {
                    subtree_paint(n, at);
                    paint_ways[at] *= paint_ways[n] + 1;
                }
            }
            for (int n : neighbors[at]) {
                if (n != prev) {
                    other_subtrees[n] = paint_ways[at] / (paint_ways[n] + 1);
                    other_subtrees[n] %= mod;
                }
            }
            paint_ways[at] %= mod;
        }

        // ok now let's actually consider literally all the other nodes
        void total_paint(int at, int prev) {
            if (at != ROOT) {
                long long prev_ways = parent_ways[prev];
                long long other_ways = other_subtrees[at];
                long long new_ways = prev_ways * other_ways % mod;
                paint_ways[at] = paint_ways[at] * (new_ways + 1) % mod;
                parent_ways[at] = (new_ways + 1) % mod;
            }
            for (int n : neighbors[at]) {
                if (n != prev) {
                    total_paint(n, at);
                }
            }
        }
    public:
        Tree(const vector<vector<int>>& neighbors, int mod = 1e9 + 7)
            : neighbors(neighbors),
              mod(mod),
              paint_ways(neighbors.size(), 1),
              parent_ways(neighbors.size()),
              other_subtrees(neighbors.size(), 1) {
            subtree_paint(ROOT, ROOT);
            parent_ways[0] = 1;
            total_paint(ROOT, ROOT);
        }

        int get_paint_ways(int start) {
            return (int) paint_ways[start];
        }
};

/**
 * https://atcoder.jp/contests/dp/tasks/dp_v
 * 4 100
 * 1 2
 * 1 3
 * 1 4 should output 8, 5, 5, and 5, each on a new line
 */
int main() {
    int node_num;
    int mod;
    std::cin >> node_num >> mod;
    vector<vector<int>> neighbors(node_num);
    for (int e = 0; e < node_num - 1; e++) {
        int n1, n2;
        std::cin >> n1 >> n2;
        neighbors[--n1].push_back(--n2);
        neighbors[n2].push_back(n1);
    }
    
    Tree tree(neighbors, mod);
    for (int n = 0; n < node_num; n++) {
        cout << tree.get_paint_ways(n) << endl;
    }
}

Submission Info

Compile Error

./Main.cpp: In constructor ‘Tree::Tree(const std::vector<std::vector<int> >&, int)’:
./Main.cpp:14:36: warning: ‘Tree::neighbors’ will be initialized after [-Wreorder]
   14 |         const vector<vector<int>>& neighbors;
      |                                    ^~~~~~~~~
./Main.cpp:13:19: warning:   ‘const int Tree::mod’ [-Wreorder]
   13 |         const int mod;
      |                   ^~~
./Main.cpp:55:9: warning:   when initialized here [-Wreorder]
   55 |         Tree(const vector<vector<int>>& neighbors, int mod = 1e9 + 7)
      |         ^~~~

Judge Result