▲ 3 r/codeforces
DP Tree - do you use bottom-up or dfs + memo?
I've solved this problem: https://atcoder.jp/contests/dp/tasks/dp_p , because I try to master every pattern in DP but it was very hard to code. What do you think? This is my bottom-up code ... I felt its overcomplicated but heard that I should focus on bottom-up afterall.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
#define for1d(i,n) for(int i = 0; i < (n); ++i)
const int MOD = 1e9 + 7;
int N = 0;
int main()
{
cin >> N;
if (N == 1)
{
cout << 2;
return 0;
}
vvll adjList(N);
vll degree(N, 0);
ll x, y;
for1d(i, N - 1)
{
cin >> x >> y;
adjList[x - 1].push_back(y - 1);
adjList[y - 1].push_back(x - 1);
degree[x - 1]++;
degree[y - 1]++;
}
vvll dp(N, vll(2, 1)); // dp[v][0] = white, dp[v][1] = black; identity until children fold in
vb visited(N, false);
queue<int> bfs;
for1d(i, N)
{
if (degree[i] == 1)
{
bfs.push(i);
}
}
int last = -1;
while (!bfs.empty())
{
int v = bfs.front();
bfs.pop();
visited[v] = true;
int p = -1;
for (int u : adjList[v])
{
if (!visited[u])
{
p = u;
break;
}
}
if (p == -1)
{
last = v;
}
else
{
dp[p][1] = (dp[p][1] * dp[v][0]) % MOD;
dp[p][0] = (dp[p][0] * (dp[v][0] + dp[v][1])) % MOD;
degree[p]--;
if (degree[p] == 1)
{
bfs.push(p);
}
else if (degree[p] == 0)
{
last = p;
}
}
}
cout << (dp[last][0] + dp[last][1]) % MOD;
return 0;
}
u/Effective_Purple1054 — 10 days ago
