Atcoder dpContest pV

unknown
c_cpp
a year ago
2.2 kB
3
Indexable
Never
```// solution for https://atcoder.jp/contests/dp/tasks/dp_v
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> edges[100001];
int m;//mod

int cnt1[100001];//以根結點開始dfs1,cnt1是節點u下面能圖色的方法數
void dfs1(int u, int pre=-1){
//u塗黑
cnt1[u] = 1;
for(int i = 0; i < edges[u].size(); i++){
int v = edges[u][i];
if(v == pre)continue;
dfs1(v, u);
cnt1[u] = cnt1[u] * cnt1[v] % m;
}
//u塗白->全部塗白
cnt1[u] = (cnt1[u]+1)%m;
}
//已經算完cnt[root]，答案是cnt[root]-1
int cnt2[100001];//連接到父節點的樹,圖色方法數
void dfs2(int u, int pre=-1){
//cnt2[v1] = 1 + {(cnt1[v1] * cnt1[v2] * cnt1[v3] * cnt1[v4]) / cnt1[v1]} * cnt2[u]
//sum1[i] = cnt1[v1] * cnt1[v2] *...* cnt1[v(i-1)]
//sum2[i] = cnt1[v(i+1)] * cnt1[v(i+2)] *...* cnt1[v(sz-1)]
//(cnt1[v1] * cnt1[v2] *... * cnt1[v(sz-1)]) / cnt1[vi] = sum1[i] * sum2[i]
//這樣複雜度是線性，又可以避免除法
int sz = edges[u].size();
vector<int> sum1(sz), sum2(sz);
sum1[0] = 1;
sum2[sz-1] = 1;

for(int i = 0; i+1 < sz; i++){
int v = edges[u][i];
if(v == pre){
sum1[i+1] = sum1[i];
continue;
}
sum1[i+1] = sum1[i] * cnt1[v] % m;
}
for(int i = sz-1; i-1 >= 0; i--){
int v = edges[u][i];
if(v == pre){
sum2[i-1] = sum2[i];
continue;
}
sum2[i-1] = sum2[i] * cnt1[v] % m;
}
for(int i = 0; i < edges[u].size(); i++){
int v = edges[u][i];
if(v == pre)continue;
cnt2[v] = (1 + sum1[i] * sum2[i] % m * cnt2[u]) % m;
dfs2(v, u);
}
}

int32_t main(){
int n;
cin >> n >> m;
for(int i = 0; i < n-1; i++){
int x,y;
cin >> x >> y;
edges[x].emplace_back(y);
edges[y].emplace_back(x);
}
dfs1(1);
cnt2[1] = 1;
if(n > 1)dfs2(1);//判斷一下n>1，不然會RE哈哈
for(int i = 1; i <= n; i++){
cout << ((cnt1[i]-1)*cnt2[i]%m+m)%m << '\n';
}
return 0;
}```