#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int N = 100002;
struct Table{
int a[2][2];
};
struct Sollution{
vector<Table> tree;
void build(int L, int R, int V)
{
if (L + 1 == R)
{
tree[V].a[0][0] = 0;
tree[V].a[0][1] = INF;
tree[V].a[1][0] = INF;
tree[V].a[1][1] = 0;
return;
}
tree[V].a[0][0] = 0;
tree[V].a[1][0] = 1;
tree[V].a[0][1] = 1;
tree[V].a[1][1] = 0;
int M = (L + R) / 2;
build(L, M, 2 * V + 1);
build(M, R, 2 * V + 2);
}
Sollution(int _n)
{
tree.resize(4 * _n);
build(0, _n, 0);
}
void __Set(int pos, int cost0, int cost1, int L, int R, int V)
{
if (L + 1 == R)
{
tree[V].a[0][0] = cost0;
tree[V].a[0][1] = INF;
tree[V].a[1][0] = INF;
tree[V].a[1][1] = cost1;
return;
}
int M = (L + R) / 2;
if (pos < M) __Set(pos, cost0, cost1, L, M, 2 * V + 1);
else __Set(pos, cost0, cost1, M, R, 2 * V + 2);
for (int le = 0; le < 2; le++)
{
for (int ri = 0; ri < 2; ri++)
{
tree[V].a[le][ri] = INF;
for (int m1 = 0; m1 < 2; m1++)
{
for (int m2 = 0; m2 < 2; m2++)
{
tree[V].a[le][ri] = min(tree[V].a[le][ri], tree[2 * V + 1].a[le][m1] + tree[2 * V + 2].a[m2][ri] + (m1 != m2));
}
}
}
}
}
void Set(int pos, int cost0, int cost1)
{
__Set(pos, cost0, cost1, 0, tree.size() / 4, 0);
}
Table Cost()
{
return tree[0];
}
};
ll n;
vector<int> graph[N];
ll x[N];
ll papa[N];
ll sz[N];
int main_child[N];
vector<int> other_child[N];
vector<vector<int> > route;
vector<Sollution> hld;
int route_pos[N];
int route_id[N];
void dfs1(int v, int p)
{
papa[v] = p;
sz[v] = 1;
for (auto u : graph[v]) if (u != p)
{
dfs1(u, v);
sz[v] += sz[u];
}
}
void dfs2(int v, int p)
{
int mxsz = 0, id = -1;
for (auto u : graph[v]) if (u != p)
{
if (sz[u] > mxsz)
{
mxsz = sz[u];
id = u;
}
}
main_child[v] = id;
for (auto u : graph[v]) if (u != p)
{
dfs2(u, v);
if (u != id) other_child[v].push_back(u);
}
}
int answer()
{
int x = INF;
Table T = hld[0].Cost();
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
x = min(x, T.a[i][j]);
}
}
return x;
}
void initialize(int n0, vector<int> a, vector<int> b)
{
n = n0;
for (int i = 0; i < n - 1; i++)
{
a[i]--, b[i]--;
graph[a[i]].push_back(b[i]);
graph[b[i]].push_back(a[i]);
}
for (int i = 0; i < n; i++)
{
x[i] = -1;
}
dfs1(0, 0);
dfs2(0, 0);
for (int i = 0; i < n; i++)
{
route_id[i] = -1;
route_pos[i] = -1;
}
for (int i = 0; i < n; i++)
{
if (route_id[i] == -1)
{
vector<int> r;
int x = i;
while (x != -1)
{
r.push_back(x);
x = main_child[x];
}
for (int j = 0; j < r.size(); j++)
{
route_id[r[j]] = route.size();
route_pos[r[j]] = j;
}
route.push_back(r);
hld.push_back(Sollution(r.size()));
}
}
}
void Set(int v, int cost0, int cost1)
{
int x = route_id[v];
int y = route_pos[v];
hld[x].Set(y, cost0, cost1);
Table T = hld[x].Cost();
int minc0 = min(T.a[0][0], T.a[0][1]);
int minc1 = min(T.a[1][0], T.a[1][1]);
int d0 = min(minc0, minc1 + 1);
int d1 = min(minc0 + 1, minc1);
v = route[x][0];
if (v == 0) return;
v = papa[v];
Set(v, d0, d1);
}
int cat(int v)
{
v--;
int c0 = 0, c1 = 0;
for (auto u : other_child[v])
{
int x = route_id[u];
Table T = hld[x].Cost();
int cost0 = min(T.a[0][0], T.a[0][1]);
int cost1 = min(T.a[1][0], T.a[1][1]);
int d0 = min(cost0, cost1 + 1);
int d1 = min(cost0 + 1, cost1);
c0 += d0, c1 += d1;
}
Set(v, c0, INF);
return answer();
}
int dog(int v)
{
v--;
int c0 = 0, c1 = 0;
for (auto u : other_child[v])
{
int x = route_id[u];
Table T = hld[x].Cost();
int cost0 = min(T.a[0][0], T.a[0][1]);
int cost1 = min(T.a[1][0], T.a[1][1]);
int d0 = min(cost0, cost1 + 1);
int d1 = min(cost0 + 1, cost1);
c0 += d0, c1 += d1;
}
Set(v, INF, c1);
return answer();
}
int neighbor(int v)
{
v--;
int c0 = 0, c1 = 0;
for (auto u : other_child[v])
{
int x = route_id[u];
Table T = hld[x].Cost();
int cost0 = min(T.a[0][0], T.a[0][1]);
int cost1 = min(T.a[1][0], T.a[1][1]);
int d0 = min(cost0, cost1 + 1);
int d1 = min(cost0 + 1, cost1);
c0 += d0, c1 += d1;
}
Set(v, c0, c1);
return answer();
}
#ifdef LOCAL
int main()
{
int n;
cin >> n;
vector<int> a(n - 1), b(n - 1);
for (int i = 0; i < n - 1; i++)
{
cin >> a[i] >> b[i];
}
initialize(n, a, b);
int q;
cin >> q;
while (q--)
{
int t, v;
cin >> t >> v;
if (t == 1) cout << cat(v) << endl;
if (t == 2) cout << dog(v) << endl;
if (t == 3) cout << neighbor(v) << endl;
}
}
#endif // LOCAL
Compilation message
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:165:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < r.size(); j++)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
