#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;
struct Data {
int dp[2][2];
Data() {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) dp[i][j] = INF;
}
}
Data(int sum1, int sum2, int type) {
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
dp[i][j] = INF;
}
}
if (type != 2) dp[0][0] = sum1;
if (type != 1) dp[1][1] = sum2;
}
};
Data merge(const Data& l, const Data& r) {
Data res = Data{};
for (int pl = 0; pl < 2; ++pl) {
for (int ql = 0; ql < 2; ++ql) {
if (l.dp[pl][ql] == INF) continue;
for (int pr = 0; pr < 2; ++pr) {
for (int qr = 0; qr < 2; ++qr) {
if (r.dp[pr][qr] == INF) continue;
int cur = l.dp[pl][ql] + r.dp[pr][qr];
if (ql != pr) ++cur;
res.dp[pl][qr] = min(res.dp[pl][qr], cur);
}
}
}
}
return res;
}
const int N = (int)1e5 + 7;
Data t[4 * N];
void upd(int v, int vl, int vr, int pos, int sum1, int sum2, int type) {
if (vr - vl == 1) {
t[v] = Data{sum1, sum2, type};
} else {
int vm = (vl + vr) / 2;
if (pos < vm) {
upd(2 * v, vl, vm, pos, sum1, sum2, type);
} else {
upd(2 * v + 1, vm, vr, pos, sum1, sum2, type);
}
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
}
Data query(int v, int vl, int vr, int l, int r) {
if (vl >= l && vr <= r) return t[v];
int vm = (vl + vr) / 2;
if (r <= vm) return query(2 * v, vl, vm, l, r);
if (vm <= l) return query(2 * v + 1, vm, vr, l, r);
return merge(query(2 * v, vl, vm, l, r), query(2 * v + 1, vm, vr, l, r));
}
void tbuild(int v, int vl, int vr) {
if (vr - vl == 1) {
t[v] = Data{0, 0, 0};
} else {
int vm = (vl + vr) / 2;
tbuild(2 * v, vl, vm);
tbuild(2 * v + 1, vm, vr);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
}
int n;
vector<int> g[N];
int a[N], b[N];
int sz[N];
int head[N];
int in[N]/*, out[N]*/, T = 0;
int cnt[N];
int type[N], sum1[N], sum2[N];
int par[N];
int find_size(int v, int p = -1) {
par[v] = p;
sz[v] = 1;
vector<int> gg;
for (int u : g[v]) {
if (u != p) {
sz[v] += find_size(u, v);
gg.push_back(u);
}
}
g[v] = gg;
return sz[v];
}
void build_hld(int v) {
for (int& u : g[v]) {
if (sz[u] > sz[g[v][0]]) swap(u, g[v][0]);
}
++cnt[head[v]];
in[v] = T++;
for (int u : g[v]) {
head[u] = u == g[v][0] ? head[v] : u;
build_hld(u);
}
//out[v] = T;
}
Data get_dp(int v) {
return query(1, 0, n, in[head[v]] - cnt[head[v]] + 1, in[v] + 1);
}
void change(int v, int s1, int s2, int type1) {
upd(1, 0, n, in[v], s1, s2, type1);
}
void init() {
find_size(0);
head[0] = 0;
for (int i = 0; i < n; ++i) cnt[i] = 0;
build_hld(0);
tbuild(1, 0, n);
for (int i = 0; i < n; ++i) {
type[i] = sum1[i] = sum2[i] = 0;
}
}
int get_ans() {
auto res1 = get_dp(0);
int res = INF;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) res = min(res, res1.dp[i][j]);
}
return res;
}
void change_type(int V, int ntype) {
int v = V;
while (v != -1) {
if (v == head[v]) {
if (par[v] == -1) break;
auto cur = get_dp(v);
int dp1 = min(cur.dp[0][0], cur.dp[1][0]);
int dp2 = min(cur.dp[0][1], cur.dp[1][1]);
sum1[par[v]] -= min(dp1, dp2 + 1);
sum2[par[v]] -= min(dp2, dp1 + 1);
v = par[v];
} else {
v = head[v];
}
}
type[V] = ntype;
v = V;
while (v != -1) {
change(v, sum1[v], sum2[v], type[v]);
if (v == head[v]) {
if (par[v] == -1) break;
auto cur = get_dp(v);
int dp1 = min(cur.dp[0][0], cur.dp[1][0]);
int dp2 = min(cur.dp[0][1], cur.dp[1][1]);
sum1[par[v]] += min(dp1, dp2 + 1);
sum2[par[v]] += min(dp2, dp1 + 1);
v = par[v];
} else {
v = head[v];
}
}
}
void initialize(int initn, vector<int> inita, vector<int> initb) {
n = initn;
for (int i = 0; i < n - 1; ++i) {
a[i] = inita[i] - 1;
b[i] = initb[i] - 1;
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
init();
}
int cat(int v) {
--v;
change_type(v, 1);
return get_ans();
}
int dog(int v) {
--v;
change_type(v, 2);
return get_ans();
}
int neighbor(int v) {
--v;
change_type(v, 0);
return get_ans();
}
#ifndef EVAL
int main() {
freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int initn;
cin >> initn;
vector<int> inita(initn - 1), initb(initn - 1);
for (int i = 0; i < initn - 1; ++i) {
cin >> inita[i] >> initb[i];
}
initialize(initn, inita, initb);
int qqq;
cin >> qqq;
while (qqq--) {
int kektype, kekv;
cin >> kektype >> kekv;
if (kektype == 1) {
cout << cat(kekv);
}
if (kektype == 2) {
cout << dog(kekv);
}
if (kektype == 3) {
cout << neighbor(kekv);
}
cout << '\n';
}
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
