/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define endl '\n'
const int N = 3e5+23, lg = 17;
ll Mod = 998244353;
inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
ll ans = 1;
a=MOD(a, mod);
while (b) {
if (b & 1) ans = MOD(ans*a, mod);
b >>= 1;
a = MOD(a*a, mod);
}
return ans;
}
struct node {
int dp[2][2];
node() {dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=0; dp[0][1]=dp[1][0]=N;}
} seg[N];
node merge(node x, node y) {
node z;
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++) {
z.dp[i][j] = min({x.dp[i][1]+y.dp[1][j], x.dp[i][0]+y.dp[0][j], x.dp[i][0]+y.dp[1][j]+1, 1+x.dp[i][1]+y.dp[0][j]});
}
}
return z;
}
int n, tim, dwn[N], tin[N], tout[N], par[N], head[N], h[N], subt[N], typ[N];
int ttmp[2][2][N];
vector<int> adj[N];
void init(int v, int p=0) {
par[v]=p, h[v]=h[p]+1, subt[v]=1;
for(int u : adj[v]) {
if(u == p) continue;
init(u, v); subt[v] += subt[u];
}
}
void dfs(int v, int p) {
int mx = 0;
tin[v] = ++tim, head[v] = p, dwn[p] = v;
for(int u : adj[v]) if(u!=par[v]) mx = (subt[mx] > subt[u] ? mx : u);
if(mx > 0) dfs(mx, p);
for(int u : adj[v]) if(u!=par[v] && u!=mx) dfs(u, u);
tout[v] = tim+1;
}
void update(int ind, node val) {
if(ind == 0) return;
if(ind >= (1<<lg)) {
seg[ind] = val;
} else {
seg[ind] = merge(seg[2*ind], seg[2*ind+1]);
}
update(ind/2, val);
}
node query(int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
if(lc>=l && rc<=r) return seg[ind];
int mid = (lc+rc)/2;
if(r<=mid) return query(l, r, 2*ind, lc, mid);
if(l>=mid) return query(l, r, 2*ind+1, mid, rc);
return merge(query(l, r, 2*ind, lc, mid), query(l, r, 2*ind+1, mid, rc));
}
void initialize(int _n, vector<int> A, vector<int> B) {
n=_n;
for(int i=0; i<n-1; i++) adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]);
init(1);
dfs(1, 1);
}
void reinit(int v) {
node ct;
while(head[v] != 1) {
ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
tmp.dp[0][0] -= min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
tmp.dp[1][0] -= min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
tmp.dp[0][1] -= min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
tmp.dp[1][1] -= min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
v=par[head[v]];
ttmp[0][0][tin[v]] -= min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
ttmp[1][0][tin[v]] -= min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
ttmp[0][1][tin[v]] -= min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
ttmp[1][1][tin[v]] -= min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
update(tin[v]+(1<<lg)-1, tmp);
}
}
int cat(int v) {
reinit(v);
typ[v] = 1;
node ct;
ct.dp[1][0]=ct.dp[1][1]=ct.dp[0][1]=n;
for(int i=0; i<2; i++) for(int j=0; j<2; j++) ct.dp[i][j] += ttmp[i][j][tin[v]];
update(tin[v]+(1<<lg)-1, ct);
while(head[v] != 1) {
ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
v=par[head[v]];
ttmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
ttmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
ttmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
ttmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
update(tin[v]+(1<<lg)-1, tmp);
}
ct = query(tin[1], tin[dwn[1]]+1);
return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]});
}
int dog(int v) {
reinit(v);
typ[v] = 2;
node ct;
ct.dp[1][0]=ct.dp[0][0]=ct.dp[0][1]=n;
for(int i=0; i<2; i++) for(int j=0; j<2; j++) ct.dp[i][j] += ttmp[i][j][tin[v]];
update(tin[v]+(1<<lg)-1, ct);
while(head[v] != 1) {
ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
v=par[head[v]];
ttmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
ttmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
ttmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
ttmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
update(tin[v]+(1<<lg)-1, tmp);
}
ct = query(tin[1], tin[dwn[1]]+1);
return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]});
}
int neighbor(int v) {
reinit(v);
typ[v] = 0;
node ct;
for(int i=0; i<2; i++) for(int j=0; j<2; j++) ct.dp[i][j] += ttmp[i][j][tin[v]];
update(tin[v]+(1<<lg)-1, ct);
while(head[v] != 1) {
ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
v=par[head[v]];
ttmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
ttmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
ttmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
ttmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
update(tin[v]+(1<<lg)-1, tmp);
}
ct = query(tin[1], tin[dwn[1]]+1);
return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]});
}
/*
int main () {
initialize(5, {1, 2, 2, 4}, {2, 3, 4, 5});
cout<<cat(3)<<endl;
cout<<dog(5)<<endl;
// tmp2 = merge(tmp2, tmp1);
// fuck(tmp2.dp[0][0]);
// fuck(tmp2.dp[1][0]);
// fuck(tmp2.dp[0][1]);
// fuck(tmp2.dp[1][1]);
cout<<cat(2)<<endl;
cout<<dog(1)<<endl;
cout<<neighbor(2)<<endl;
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24156 KB |
Output is correct |
| 2 |
Correct |
5 ms |
26204 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
26204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24156 KB |
Output is correct |
| 2 |
Correct |
5 ms |
26204 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
26204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24156 KB |
Output is correct |
| 2 |
Correct |
5 ms |
26204 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
26204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
