#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5 + 7;
const int INF = (int) 1e8;
int n, sub[N], child[N], color[N], par[N], y, dp1[N], dp2[N], cost1[N], cost2[N], index[N], curind, node[N], l1[N], l2[N];
vector<int> members[N];
bool isTheChild[N];
vector<int> g[N];
struct D {
bool nmc;
int cost[2][2];
};
D operator + (D a, D b) {
if (a.nmc) {
return b;
}
if (b.nmc) {
return a;
}
D c;
c.nmc = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c.cost[i][j] = INF;
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
for (int l = 0; l < 2; l++) {
c.cost[i][l] = min(c.cost[i][l], a.cost[i][j] + b.cost[k][l] + (j != k));
}
}
}
}
return c;
}
D t[4 * N];
D wnmc;
void upd(int v, int tl, int tr, int i) {
if (tr < i || i < tl) {
return;
}
if (tl == tr) {
vector<int> K = {cost1[node[i]] + dp1[node[i]], cost2[node[i]] + dp2[node[i]]};
t[v].cost[0][1] = t[v].cost[1][0] = INF;
t[v].cost[0][0] = K[0];
t[v].cost[1][1] = K[1];
return;
}
int tm = (tl + tr) / 2;
upd(2 * v, tl, tm, i);
upd(2 * v + 1, tm + 1, tr, i);
t[v] = t[2 * v] + t[2 * v + 1];
}
D get(int v, int tl, int tr, int l, int r) {
if (tr < l || r < tl) {
return wnmc;
}
if (l <= tl && tr <= r) {
return t[v];
}
int tm = (tl + tr) / 2;
D x = get(2 * v, tl, tm, l, r);
D y = get(2 * v + 1, tm + 1, tr, l, r);
D z = x + y;
return x + y;
}
void buildtr(int v = 1, int tl = 0, int tr = n) {
if (tl == tr) {
t[v].cost[0][1] = t[v].cost[1][0] = INF;
t[v].cost[0][0] = t[v].cost[1][1] = 0;
} else {
int tm = (tl + tr) / 2;
buildtr(2 * v, tl, tm);
buildtr(2 * v + 1, tm + 1, tr);
t[v] = t[2 * v] + t[2 * v + 1];
}
}
int getdp1(int l, int r) {
D sol = get(1, 0, n, l, r);
return min(sol.cost[0][0], sol.cost[0][1]);
}
int getdp2(int l, int r) {
D sol = get(1, 0, n, l, r);
return min(sol.cost[1][0], sol.cost[1][1]);
}
void build(int a, int p = 0) {
vector<int> kids;
sub[a] = 1;
par[a] = p;
for (auto &b : g[a]) {
if (b != p) {
kids.push_back(b);
build(b, a);
sub[a] += sub[b];
if (sub[b] > sub[child[a]]) {
child[a] = b;
}
}
}
isTheChild[child[a]] = 1;
g[a] = kids;
}
void compute(int a) {
if (isTheChild[a]) {
color[a] = color[par[a]];
} else {
color[a] = ++y;
}
index[a] = ++curind;
node[index[a]] = a;
members[color[a]].push_back(a);
if (child[a]) {
compute(child[a]);
for (auto &b : g[a]) {
if (b != child[a]) {
compute(b);
}
}
}
}
void updVertex(int v) {
int p = par[members[color[v]][0]];
dp1[p] -= l1[color[v]];
dp2[p] -= l2[color[v]];
upd(1, 0, n, index[v]);
l1[color[v]] = getdp1(index[members[color[v]][0]], index[members[color[v]].back()]);
l2[color[v]] = getdp2(index[members[color[v]][0]], index[members[color[v]].back()]);
l1[color[v]] = min(l1[color[v]], l2[color[v]] + 1);
l2[color[v]] = min(l2[color[v]], l1[color[v]] + 1);
dp1[p] += l1[color[v]];
dp2[p] += l2[color[v]];
}
void update(int node) {
while (node) {
for (int j = 1; j < (int) members[color[node]].size(); j++) {
assert(index[members[color[node]][j - 1]] == index[members[color[node]][j]] - 1);
}
int p = par[members[color[node]][0]];
int i1 = getdp1(index[members[color[node]][0]], index[members[color[node]].back()]), i2 = getdp2(index[members[color[node]][0]], index[members[color[node]].back()]);
updVertex(node);
node = p;
}
}
void initialize(int nn, std::vector<int> edgesA, std::vector<int> edgesB) {
wnmc.nmc = 1;
n = nn;
buildtr();
for (int i = 0; i < n - 1; i++) {
int a = edgesA[i];
int b = edgesB[i];
g[a].push_back(b);
g[b].push_back(a);
}
build(1);
compute(1);
}
void changeCost(int v, int c1, int c2) {
dp1[v] -= cost1[v];
dp2[v] -= cost2[v];
cost1[v] = c1;
cost2[v] = c2;
dp1[v] += cost1[v];
dp2[v] += cost2[v];
updVertex(v);
update(v);
}
int eval() {
return min(dp1[0], dp2[0]);
}
int cat(int v) {
changeCost(v, 0, INF);
return eval();
}
int dog(int v) {
changeCost(v, INF, 0);
return eval();
}
int neighbor(int v) {
changeCost(v, 0, 0);
return eval();
}
Compilation message
catdog.cpp:8:90: error: 'int index [100007]' redeclared as different kind of entity
8 | int n, sub[N], child[N], color[N], par[N], y, dp1[N], dp2[N], cost1[N], cost2[N], index[N], curind, node[N], l1[N], l2[N];
| ^
In file included from /usr/include/string.h:432,
from /usr/include/c++/10/cstring:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
from catdog.cpp:2:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
61 | index (const char *__s, int __c) __THROW
| ^~~~~
catdog.cpp: In function 'void compute(int)':
catdog.cpp:124:8: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
124 | index[a] = ++curind;
| ^
catdog.cpp:125:13: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
125 | node[index[a]] = a;
| ^
catdog.cpp: In function 'void updVertex(int)':
catdog.cpp:143:21: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
143 | upd(1, 0, n, index[v]);
| ^
catdog.cpp:145:30: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
145 | l1[color[v]] = getdp1(index[members[color[v]][0]], index[members[color[v]].back()]);
| ^
catdog.cpp:145:59: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
145 | l1[color[v]] = getdp1(index[members[color[v]][0]], index[members[color[v]].back()]);
| ^
catdog.cpp:146:30: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
146 | l2[color[v]] = getdp2(index[members[color[v]][0]], index[members[color[v]].back()]);
| ^
catdog.cpp:146:59: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
146 | l2[color[v]] = getdp2(index[members[color[v]][0]], index[members[color[v]].back()]);
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from catdog.cpp:2:
catdog.cpp: In function 'void update(int)':
catdog.cpp:161:19: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
161 | assert(index[members[color[node]][j - 1]] == index[members[color[node]][j]] - 1);
| ^
catdog.cpp:161:57: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
161 | assert(index[members[color[node]][j - 1]] == index[members[color[node]][j]] - 1);
| ^
catdog.cpp:166:26: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
166 | int i1 = getdp1(index[members[color[node]][0]], index[members[color[node]].back()]), i2 = getdp2(index[members[color[node]][0]], index[members[color[node]].back()]);
| ^
catdog.cpp:166:58: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
166 | int i1 = getdp1(index[members[color[node]][0]], index[members[color[node]].back()]), i2 = getdp2(index[members[color[node]][0]], index[members[color[node]].back()]);
| ^
catdog.cpp:166:9: warning: unused variable 'i1' [-Wunused-variable]
166 | int i1 = getdp1(index[members[color[node]][0]], index[members[color[node]].back()]), i2 = getdp2(index[members[color[node]][0]], index[members[color[node]].back()]);
| ^~
