/*input
3
1 2 1
2 3 1
3 1 2
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int V[101010];
vector<int>adj[101010];
int pa[101010];
int sz[101010];
void dfs(int i, int p)
{
if (p != 0)
{
adj[i].erase(find(adj[i].begin(), adj[i].end(), p));
}
pa[i] = p;
sz[i] = 1;
pair<int, int>mx = { -1, -1};
for (int t = 0; t < (int)adj[i].size(); t++)
{
int j = adj[i][t];
dfs(j, i);
sz[i] += sz[j];
mx = max(mx, {sz[j], t});
}
if (mx.second != -1)
{
swap(adj[i][0], adj[i][mx.second]);
}
}
int head[101010];
int timer = 1;
int nr[101010];
int tail[101010];
void hld(int i, int h)
{
nr[i] = timer++;
head[i] = h;
tail[h] = i;
for (int t = 0; t < (int)adj[i].size(); t++)
{
int j = adj[i][t];
hld(j, t == 0 ? h : j);
}
}
struct line
{
int cc = 0, cd = 0, dd = 0, dc = 0;
};
line merge(line a, line b)
{
line c;
c.cc = min({a.cc + b.cc, a.cc + b.dc + 1, a.cd + b.cc + 1, a.cd + b.dc});
c.cd = min({a.cc + b.cd, a.cc + b.dd + 1, a.cd + b.cd + 1, a.cd + b.dd});
c.dd = min({a.dc + b.cd, a.dc + b.dd + 1, a.dd + b.cd + 1, a.dd + b.dd});
c.dc = min({a.dc + b.cc, a.dc + b.dc + 1, a.dd + b.cc + 1, a.dd + b.dc});
return c;
}
struct ST
{
line X;
int l, r;
ST *left, *right;
ST(int l, int r): l(l), r(r)
{
if (l < r)
{
left = new ST(l, (l + r) / 2);
right = new ST((l + r) / 2 + 1, r);
X = merge(left->X, right->X);
}
else
{
X.cc = 0;
X.cd = 101010;
X.dc = 101010;
X.dd = 0;
}
}
line get(int x, int y)
{
if (x <= l && r <= y)
return X;
if (r < x || y < l)
return line();
return merge(left->get(x, y), right->get(x, y));
}
void setC(int x, int w)
{
if (l == r)
{
X.cc = w;
}
else
{
if (x <= (l + r) / 2)
left->setC(x, w);
else
right->setC(x, w);
X = merge(left->X, right->X);
}
}
void setD(int x, int w)
{
if (l == r)
{
X.dd = w;
}
else
{
if (x <= (l + r) / 2)
left->setD(x, w);
else
right->setD(x, w);
X = merge(left->X, right->X);
}
}
} medis(0, 101010);
void initialize(int N, vector<int> A, vector<int> B)
{
for (int i = 0; i < N - 1; i++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1, 0);
hld(1, 1);
}
int C[101010], D[101010];
void fix(int v)
{
int w = head[v];
line X = medis.get(nr[w], nr[tail[w]]);
C[pa[w]] -= min(X.cd, X.cc);
D[pa[w]] -= min(X.dd, X.dc);
if (V[v] == -1)
{
medis.setC(nr[v], min(C[v], D[v] + 1));
medis.setD(nr[v], 101010);
} else if (V[v] == 1)
{
medis.setC(nr[v], 101010);
medis.setD(nr[v], min(D[v], C[v] + 1));
} else
{
medis.setC(nr[v], min(C[v], D[v] + 1));
medis.setD(nr[v], min(D[v], C[v] + 1));
}
X = medis.get(nr[w], nr[tail[w]]);
C[pa[w]] += min(X.cd, X.cc);
D[pa[w]] += min(X.dd, X.dc);
if (v != w)
return fix(w);
else if (v != 1)
return fix(pa[v]);
}
int cat(int v)
{
V[v] = -1;
fix(v);
return min(C[0], D[0]);
}
int dog(int v)
{
V[v] = 1;
fix(v);
return min(C[0], D[0]);
}
int neighbor(int v)
{
V[v] = 0;
fix(v);
return min(C[0], D[0]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
12152 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
12280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
12152 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
12280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
12152 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
12280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
