Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int int64_t
- const int inf = 2e18;
- //const int mod = 1e9 + 7;
- int mod;
- vector<vector<int>> g;
- vector<int> dp;
- void count_dp(int v, int p) {
- dp[v] = 1;
- for (int to: g[v]) {
- if (to == p) {
- continue;
- }
- count_dp(to, v);
- (dp[v] *= dp[to] + 1) %= mod;
- }
- }
- vector<int> ans;
- void reroot(int v, int p, int dp_super) {
- ans[v] = dp[v] * (dp_super + 1) % mod;
- vector<int> sons;
- for (int to: g[v]) {
- if (to == p) {
- continue;
- }
- sons.push_back(to);
- }
- vector<int> pref(sons.size() + 1, 1);
- for (int i = 0; i < sons.size(); i++) {
- pref[i + 1] = pref[i] * (dp[sons[i]] + 1) % mod;
- }
- vector<int> suf(sons.size() + 1, 1);
- for (int i = int(sons.size()) - 1; i >= 0; i--) {
- suf[i] = suf[i + 1] * (dp[sons[i]] + 1) % mod;
- }
- for (int i = 0; i < sons.size(); i++) {
- reroot(sons[i], v, pref[i] * suf[i + 1] % mod * (dp_super + 1) % mod);
- }
- }
- int32_t main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int n;
- cin >> n >> mod;
- g.resize(n);
- for (int i = 0; i < n - 1; i++) {
- int a, b;
- cin >> a >> b;
- a--; b--;
- g[a].push_back(b);
- g[b].push_back(a);
- }
- dp.resize(n);
- count_dp(0, -1);
- ans.resize(n);
- reroot(0, -1, 0);
- for (int x: ans) {
- cout << x << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment