Submission #61496610

---

Source Code Expand

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using ll=long long;
using ull=unsigned long long;

#include <atcoder/all>
using namespace atcoder;
using mint=modint;

#define rep(i, e) for(int i=0; i<(int)(e); ++i)
#define dir(dx, dy) for(auto [dx, dy]: vector{pair{1, 0}, {0, 1}, {-1, 0}, {0, -1}})

#define all(v) (v).begin(), (v).end()
#define all_r(v) (v).rbegin(), (v).rend()

#define in(i) cin >> i
#define in_d(type, i) type i; cin >> i
#define in_z(i) cin >> i; --i
#define in_d_z(type, i) type i; cin >> i; --i
#define out(i) cout << (i) << endl
#define err(i) cerr << (i) << endl
#define out_e() cout << endl
#define err_e() cerr << endl
#define out_s(i) cout << (i) << " "
#define err_s(i) cerr << (i) << " "

#define out_f(i) cout << fixed << setprecision(15) << (i) << endl
#define err_f(i) cerr << fixed << setprecision(15) << (i) << endl
#define out_fs(i) cout << fixed << setprecision(15) << (i) << " "
#define err_fs(i) cerr << fixed << setprecision(15) << (i) << " "

constexpr int max32=1'000'000'000;
constexpr ll max64=1'000'000'000'000'000'000;

template <typename T>
bool chmin(T & l, const T & r) {
    if(r<l){
        l=r;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T & l, const T & r) {
    if(r>l){
        l=r;
        return true;
    }
    return false;
}

void dfs_1(int v, vector<vector<int>> & g, vector<bool> & seen, vector<vector<mint>> & dp, vector<vector<vector<mint>>> & reroot){
    int sz=g[v].size();
    dp[v]={1, 1};
    rep(i, sz){
        int u=g[v][i];
        if(seen[u]){
            swap(g[v][i], g[v][0]);
            break;
        }
    }
    rep(i, sz){
        int u=g[v][i];
        if(seen[u]){
            continue;
        }
        seen[u]=true;
        dfs_1(u, g, seen, dp, reroot);
        reroot[v][i]=dp[u];
        dp[v][0]*=dp[u][0];
        dp[v][1]*=dp[u][0]+dp[u][1];
    }
}

void dfs_2(int v, vector<vector<int>> & g, vector<bool> & seen, vector<mint> & ans, vector<vector<vector<mint>>> & reroot){
    int sz=g[v].size();
    vector left(sz+1, vector<mint>(2, 1));
    vector right(sz+1, vector<mint>(2, 1));
    rep(i, sz){
        left[i+1][0]=left[i][0]*reroot[v][i][0];
        left[i+1][1]=left[i][1]*(reroot[v][i][0]+reroot[v][i][1]);
    }
    for(int i=sz-1;i>=0;--i){
        right[i][0]=right[i+1][0]*reroot[v][i][0];
        right[i][1]=right[i+1][1]*(reroot[v][i][0]+reroot[v][i][1]);
    }
    ans[v]=right[0][1];
    rep(i, sz){
        int u=g[v][i];
        if(seen[u]){
            continue;
        }
        seen[u]=true;
        reroot[u][0][0]=left[i][0]*right[i+1][0];
        reroot[u][0][1]=left[i][1]*right[i+1][1];
        dfs_2(u, g, seen, ans, reroot);
    }
}

int main(void) {
    in_d(int, n);
    in_d(int, m);
    mint::set_mod(m);
    vector<int> x(n-1);
    vector<int> y(n-1);
    vector g(n, vector<int>());
    rep(i, n-1){
        in_z(x[i]);
        in_z(y[i]);
        g[x[i]].emplace_back(y[i]);
        g[y[i]].emplace_back(x[i]);
    }
    vector<bool> seen_1(n);
    vector dp(n, vector<mint>(2));
    vector<mint> ans(n);
    vector reroot(n, vector<vector<mint>>());
    rep(i, n){
        reroot[i].resize(g[i].size(), vector<mint>(2));
    }
    seen_1[0]=true;
    dfs_1(0, g, seen_1, dp, reroot);
    vector<bool> seen_2(n);
    seen_2[0]=true;
    dfs_2(0, g, seen_2, ans, reroot);
    rep(i, n){
        out(ans[i].val());
    }
    return 0;
}

Submission Info

Judge Result