#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF1 = 1e9 + 100;
constexpr ll INF2 = 4e18;
int n;
vector<int> adj[100100], G[100100];
int par[100100], sz[100100], in[100100], top[100100], leaf[100100], typ[100100], cnt;
array<ll, 2> A[100100], C[100100], D[100100];
void operator += (array<ll, 2> &L, const array<ll, 2> &R){
L[0] += R[0], L[1] += R[1];
}
void operator -= (array<ll, 2> &L, const array<ll, 2> &R){
L[0] -= R[0], L[1] -= R[1];
}
struct M{
ll a[2][2];
M(){}
M(ll _x, ll _y, ll _z, ll _w){
a[0][0] = _x;
a[0][1] = _y;
a[1][0] = _z;
a[1][1] = _w;
}
array<ll, 2> calc(const array<ll, 2> &x) const{
return {min(x[0]+a[0][0], x[1]+a[1][0]), min(x[0]+a[0][1], x[1]+a[1][1])};
}
M operator + (const M &F) const{
M ret(INF2, INF2, INF2, INF2);
for (int i=0;i<2;i++){
for (int j=0;j<2;j++){
for (int k=0;k<2;k++) ret.a[i][k] = min(ret.a[i][k], a[i][j] + F.a[j][k]);
}
}
return ret;
}
};
struct Seg{
M tree[200200];
int sz;
void init(int n){
sz = n;
for (int i=sz;i<sz*2;i++) tree[i] = M(0, 1, 1, 0);
for (int i=sz-1;i;i--) tree[i] = tree[i<<1] + tree[i<<1|1];
}
void update(int p, const array<ll, 2> &x){
p += sz;
tree[p] = M(x[0], x[1]+1, x[0]+1, x[1]);
for (p>>=1;p;p>>=1) tree[p] = tree[p<<1] + tree[p<<1|1];
}
M query(int l, int r){
// printf("query %d %d\n", l, r);
++r;
M retL(0, INF2, INF2, 0), retR(0, INF2, INF2, 0);
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) retL = retL + tree[l++];
if (r&1) retR = tree[--r] + retR;
}
// printf("(%lld, %lld, %lld, %lld)\n", retL.a[0][0], retL.a[0][1], retL.a[1][0], retL.a[1][1]);
// printf("(%lld, %lld, %lld, %lld)\n", retR.a[0][0], retR.a[0][1], retR.a[1][0], retR.a[1][1]);
// auto ret = retL + retR;
// printf("(%lld, %lld, %lld, %lld)\n", ret.a[0][0], ret.a[0][1], ret.a[1][0], ret.a[1][1]);
return retL + retR;
}
}tree;
void dfs0(int s, int pa = 0){
par[s] = pa;
sz[s] = 1;
for (auto &v:adj[s]) if (v!=pa){
G[s].push_back(v);
dfs0(v, s);
sz[s] += sz[v];
}
}
void dfs1(int s){
in[s] = ++cnt;
if (G[s].empty()){
leaf[top[s]] = s;
return;
}
swap(G[s][0], *max_element(G[s].begin(), G[s].end(), [&](int x, int y){return sz[x] < sz[y];}));
for (auto &v:G[s]){
if (v==G[s][0]) top[v] = top[s];
else top[v] = v;
dfs1(v);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
cnt = 0;
for (int i=0;i<N-1;i++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
top[1] = 1;
dfs0(1);
dfs1(1);
fill(::A+1, ::A+n+1, array<ll, 2>{0, 0});
fill(C+1, C+n+1, array<ll, 2>{0, 0});
fill(D+1, D+n+1, array<ll, 2>{0, 0});
fill(typ+1, typ+n+1, 0);
tree.init(n+1);
// printf("ok\n");
}
void update(int x){
C[x] -= A[x];
if (typ[x]==0) A[x] = {0, 0};
else if (typ[x]==1) A[x] = {0, INF1};
else A[x] = {INF1, 0};
C[x] += A[x];
tree.update(in[x], C[x]);
while(true){
x = top[x];
if (x!=1) C[par[x]] -= array<ll, 2>{min(D[x][0], D[x][1]+1), min(D[x][0]+1, D[x][1])};
D[x] = tree.query(in[x], in[leaf[x]]).calc({0, 0});
if (x!=1) C[par[x]] += array<ll, 2>{min(D[x][0], D[x][1]+1), min(D[x][0]+1, D[x][1])};
else break;
x = par[x];
tree.update(in[x], C[x]);
}
// printf("ok done ans = %lld\n", min(D[1][0], D[1][1]));
// printf("top: ");
// for (int i=1;i<=n;i++) printf("%d ", top[i]);
// printf("\n");
// printf("A: ");
// for (int i=1;i<=n;i++) printf("(%lld, %lld) ", A[i][0], A[i][1]);
// printf("\n");
// printf("C: ");
// for (int i=1;i<=n;i++) printf("(%lld, %lld) ", C[i][0], C[i][1]);
// printf("\n");
// printf("D: ");
// for (int i=1;i<=n;i++) printf("(%lld, %lld) ", D[i][0], D[i][1]);
// printf("\n");
}
int cat(int v) {
typ[v] = 1;
update(v);
return min(D[1][0], D[1][1]);
}
int dog(int v) {
typ[v] = 2;
update(v);
return min(D[1][0], D[1][1]);
}
int neighbor(int v) {
typ[v] = 0;
update(v);
return min(D[1][0], D[1][1]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
