Помогите найти багу в коде.
Идея такова:
Для дерева ответ будем хранить в дпшке dp[v][0, 1]; это максимальный ответ для поддерева вершины если она закрашена и не закрашена.
Так как из одной вершины в другие может исходить максимум только 1 ребро компонента это будет либо дерево, либо деревья подвешенные на вершины образующие циклы. Чтобы найти ответ для каждой компоненты следует сперва найти ответ для каждого дерева в цикле. Потом написать отдельную дпшку на цикле pd[i][1, 0][1, 0]; pd[i][1][1] это ответ для текущей вершины в цикле если она закрашена и первый элемент цикла закрашен. Первая единичка отвечает за текущюю вершину а вторая за начало цикла. У меня падают тесты в 1 группе где n <= 20;
vector<int> g[3 * N];
vector<vector<int>> cycles;
// dp ответ для деревьев. dp[v][0] макс ответ если вершина v закрашена и если 1 то наоборот
// pd ответ для цикла. Состояние pd[i][1][1] это макс ответ если вершина i закрашена и начало цикла закрашено.
// pd[i][отвечает за текущюю вершину в цикле][за начало цикла]
ll dp[3 * N][2], a[3 * N], pd[3 * N][2][2];
//if sus[v] = true vertex v is part of the cycle
bool sus[3 * N], was[3 * N];
int used[3 * N], p[3 * N];
//start and end of the cycles
int st, en;
//нахождение цикла
bool cyc(int v) {
used[v] = 1;
for(int u : g[v]) {
if(!used[u]) {
if(cyc(u))return 1;
} else if(used[u] == 1) {
st = u;
en = v;
return 1;
}
}
used[v] = 2;
return 0;
}
// нахождение ответа для дерева которое подвешено на одну из вершин цикла
void dfs(int v) {
dp[v][1] = 1;
dp[v][0] = 0;
was[v] = 1;
for(int u : g[v]) {
if(sus[u])continue;
dfs(u);
dp[v][0] += max(dp[u][1], dp[u][0]);
dp[v][1] += dp[u][0];
}
}
void yela() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] != -1) {
g[a[i]].pb(i);
p[i] = a[i];
}
}
ll ans = 0;
for(int i = 1; i <= n; i++) {
if(!used[i]) {
if(cyc(i)) {
vector<int> cur;
for(int j = en; j != st && j != 0; j = p[j]) {
cur.pb(j);
sus[j] = 1;
}
cur.pb(st);
sus[st] = 1;
cycles.pb(cur);
st = 0;
en = 0;
}
}
}
for(auto c : cycles) {
for(auto i : c) {
dfs(i);
}
int pr = -1;
pd[c[0]][1][1] = dp[c[0]][1];
pd[c[0]][0][0] = dp[c[0]][0];
for(auto i : c) {
if(pr == -1) {
pr = c[0];
continue;
}
pd[i][1][1] = pd[pr][0][1] + dp[i][1];
pd[i][1][0] = pd[pr][0][0] + dp[i][1];
if(pr != c[0])
pd[i][0][0] = max(pd[pr][1][0], pd[pr][0][0]) + dp[i][0];
else {
pd[i][0][0] = pd[pr][0][0] + dp[i][0];
}
if(pr != c[0])
pd[i][0][1] = max(pd[pr][1][1], pd[pr][0][1]) + dp[i][0];
else
pd[i][0][1] = pd[pr][1][1] + dp[i][0];
pr = i;
}
ans += max({pd[pr][0][0], pd[pr][0][1], pd[pr][1][0], pd[pr][1][1]});
}
for(int i = 1; i <= n; i++) {
if(!was[i]) {
int r = i;
while(p[r] != 0) {
r = p[r];
}
dfs(r);
ans += max(dp[r][0], dp[r][1]);
}
}
cout << ans << "\n";
}