#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define mat array<array<int, 2>, 2>
const int mx = 1e5 + 5;
int state[mx], par[mx], sz[mx], dep[mx], root[mx], id[mx], psz[mx]; vector<int> adj[mx];
struct segTree{
int sz = 0; vector<mat> seg;
void init(int sz_){
sz = sz_ + 1; seg.resize(sz * 2, {});
FOR(i, sz, sz * 2) seg[i][0][1] = seg[i][1][0] = 1e9;
}
void comb(mat &cur, mat A, mat B){
FOR(i, 0, 2) FOR(j, 0, 2) cur[i][j] = 1e9;
FOR(i, 0, 2) FOR(j, 0, 2) FOR(k, 0, 2) FOR(l, 0, 2)
cur[i][j] = min(cur[i][j], B[i][k] + A[l][j] + (k != l));
}
void apply(int i, int dt0, int dt1){
i += sz;
seg[i][0][0] += dt0;
seg[i][1][1] += dt1;
while (i /= 2) comb(seg[i], seg[i * 2], seg[i * 2 + 1]);
}
void getBestTop(int &A, int &B){
int top0 = min(seg[1][0][0], seg[1][0][1]);
int top1 = min(seg[1][1][0], seg[1][1][1]);
A = min(top0, top1 + 1);
B = min(top0 + 1, top1);
}
}trees[mx];
void dfsSZ(int u){
sz[u] = 1;
for (int &v : adj[u]) if (v != par[u]){
par[v] = u; dep[v] = dep[u] + 1;
dfsSZ(v);
sz[u] += sz[v];
if (sz[v] > sz[adj[u][0]]) swap(v, adj[u][0]);
}
}
void dfsHLD(int u){
id[u] = psz[root[u]]++;
for (int v : adj[u]) if (v != par[u]){
root[v] = (v == adj[u][0] ? root[u] : v);
dfsHLD(v);
}
}
int updSolve(int u, int col, int dt0, int dt1){
state[u] = col;
while (u){
int b0, b1, n0, n1, R = root[u];
trees[R].getBestTop(b0, b1);
trees[R].apply(id[u], dt0, dt1);
trees[R].getBestTop(n0, n1);
dt0 = n0 - b0; dt1 = n1 - b1;
u = par[R];
}
int ret0, ret1; trees[1].getBestTop(ret0, ret1);
return min(ret0, ret1);
}
void initialize(int n, vector<int> A, vector<int> B){
FOR(i, 0, n - 1){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
root[1] = id[1] = 1; dfsSZ(1); dfsHLD(1);
FOR(i, 1, n + 1){
trees[i].init(psz[i]);
id[i] = psz[root[i]] - id[i] - 1;
}
}
int cat(int i){ return updSolve(i, 0, 0, mx); }
int dog(int i){ return updSolve(i, 1, mx, 0); }
int neighbor(int i){ return !state[i] ? updSolve(i, 0, 0, -mx) : updSolve(i, 1, -mx, 0); }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5708 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5708 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5708 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
