1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <cstdio>
#include <vector>
#define pb push_back
using namespace std;
typedef long long L;
const int N = 1e5 + 10;
int n, m, f[N], g[N], h[N];
vector <int> e[N];
void dfs1 (int u, int fa)
{
f[u] = 1;
for (int v : e[u]) if (v ^ fa)
{
dfs1(v, u);
f[u] = f[u] * (f[v] + 1ll) % m;
}
}
void dfs2 (int u, int fa)
{
if (e[u].empty()) return;
vector <int> a(e[u].size()), b(e[u].size());
a.front() = (e[u].front() == fa ? 0 : f[e[u].front()]) + 1;
b.back() = (e[u].back() == fa ? 0 : f[e[u].back()]) + 1;
for (int i = 1; i < e[u].size(); ++i)
if (e[u][i] == fa) a[i] = a[i - 1];
else a[i] = a[i - 1] * (f[e[u][i]] + 1ll) % m;
for (int i = e[u].size() - 2; ~i; --i)
if (e[u][i] == fa) b[i] = b[i + 1];
else b[i] = b[i + 1] * (f[e[u][i]] + 1ll) % m;
for (int i = 0; i < e[u].size(); ++i) if (e[u][i] ^ fa)
{
h[e[u][i]] = (h[u] + 1ll) * (i ? a[i - 1] : 1) % m * (i < e[u].size() - 1 ? b[i + 1] : 1) % m ;
g[e[u][i]] = ((L)g[u] + f[e[u][i]] - h[e[u][i]]) % m;
dfs2(e[u][i], u);
}
}
int main ()
{
scanf("%d%d", &n, &m);
for (int i = 1, a, b; i < n; ++i)
scanf("%d%d", &a, &b), e[a].pb(b), e[b].pb(a);
dfs1(1, 0);
g[1] = f[1], h[1] = 0;
dfs2(1, 0);
for (int i = 1; i <= n; ++i)
printf("%d\n", (g[i] + m) % m);
return 0;
}
|