#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> adj[N];
int par[N], chain[N], head[N], tail[N], tin[N], sz[N];
int tchain = 0, tcur = 0, n;
void dfs_size(int x, int p) {
sz[x] = 1;
par[x] = p;
for (int y: adj[x]) {
if (y == p) continue;
dfs_size(y, x);
sz[x] += sz[y];
}
}
void dfs(int x) {
tin[x] = ++tcur;
if (!chain[x]) {
chain[x] = ++tchain;
head[tchain] = x;
}
tail[chain[x]] = x;
int spec = -1;
for (int y: adj[x]) {
if (y == par[x]) continue;
if (spec == -1 || sz[y] > sz[spec])
spec = y;
}
if (spec != -1) {
chain[spec] = tchain;
dfs(spec);
}
for (int y: adj[x])
if (y != par[x] && y != spec)
dfs(y);
}
void initialize(int n, vector<int> A, vector<int> B) {
::n = n;
for (int i = 0; i < n - 1; i++) {
int x = A[i], y = B[i];
adj[x].emplace_back(y);
adj[y].emplace_back(x);
}
dfs_size(1, 0);
dfs(1);
}
const int INF = 1e9;
struct Node {
int val[2][2];
Node() = default;
Node(bool set_inf) {
if (set_inf) {
for (int a: {0, 1})
for (int b: {0, 1})
val[a][b] = INF;
}
}
void debug() {
cerr << string(10, '=') << '\n';
for (int a: {0, 1}) for (int b: {0, 1})
fprintf(stderr, "val[%d][%d] = %d\n", a, b, val[a][b]);
cerr << string(10, '=') << "\n\n";
}
int res() const {
int ans = INF;
for (int a: {0, 1})
for (int b: {0, 1})
ans = min(ans, val[a][b]);
return ans;
}
Node operator + (const Node &other) const {
Node ans;
for (int a = 0; a < 2; a++) {
for (int d = 0; d < 2; d++) {
int cur = INF;
for (int b = 0; b < 2; b++)
for (int c = 0; c < 2; c++)
cur = min(cur, val[a][b] + other.val[c][d] + (b != c));
ans.val[a][d] = cur;
}
}
return ans;
}
} IT[N << 2];
int dp[N][2]; // only consider vertices NOT in heavy chain, segment tree will consider the rest + dp
int up_par[N][2]; // for chain_head to update dp[par]'s values
Node node_inf(true);
void update_color(int x, int c, int id, int l, int r) {
if (l == r) {
// if (c ^ color) == 0 => skip
IT[id] = node_inf;
for (int col: {0, 1})
if ((col + 1) ^ c)
IT[id].val[col][col] = dp[x][col];
// cerr << "x = " << x << '\n';
// IT[id].debug();
return;
}
int mid = (l + r) / 2;
if (x <= mid) update_color(x, c, id << 1, l, mid);
else update_color(x, c, id << 1 | 1, mid + 1, r);
IT[id] = IT[id << 1] + IT[id << 1 | 1];
}
void update_val(int x, int w[], int id, int l, int r) {
if (l == r) {
for (int col: {0, 1})
if (IT[id].val[col][col] != INF)
IT[id].val[col][col] += w[col];
return;
}
int mid = (l + r) / 2;
if (x <= mid) update_val(x, w, id << 1, l, mid);
else update_val(x, w, id << 1 | 1, mid + 1, r);
IT[id] = IT[id << 1] + IT[id << 1 | 1];
}
Node get_range(int x, int y, int id, int l, int r) {
if (l > y || r < x) return Node();
if (x <= l && r <= y) return IT[id];
int mid = (l + r) / 2;
return get_range(x, y, id << 1, l, mid) + get_range(x, y, id << 1 | 1, mid + 1, r);
}
int get(int x) {
int xchain = chain[x], head_ = head[xchain], tail_ = tail[xchain];
while (xchain != 1) {
auto S = get_range(tin[head_], tin[tail_], 1, 1, n);
int val[] = {min(S.val[0][0], S.val[0][1]), min(S.val[1][0], S.val[1][1])};
int upd[] = {-up_par[head_][0] + min(val[0], val[1] + 1),
-up_par[head_][1] + min(val[0] + 1, val[1])};
update_val(tin[par[head_]], upd, 1, 1, n);
up_par[head_][0] = min(val[0], val[1] + 1);
up_par[head_][1] = min(val[0] + 1, val[1]);
tail_ = par[head_];
xchain = chain[tail_];
head_ = head[xchain];
}
return get_range(tin[head_], tin[tail_], 1, 1, n).res();
}
int solve(int s, int c) {
update_color(tin[s], c, 1, 1, n);
return get(s);
}
int cat(int v) {
return solve(v, 2);
}
int dog(int v) {
return solve(v, 1);
}
int neighbor(int v) {
return solve(v, 0);
}
#ifdef LOCAL
int readInt(){
int i;
if(scanf("%d",&i)!=1){
fprintf(stderr,"Error while reading input\n");
exit(1);
}
return i;
}
int main(){
int N=readInt();
std::vector<int> A(N-1),B(N-1);
for(int i=0;i<N-1;i++)
{
A[i]=readInt();
B[i]=readInt();
}
int Q;
assert(scanf("%d",&Q)==1);
std::vector <int> T(Q),V(Q);
for(int i=0;i<Q;i++)
{
T[i]=readInt();
V[i]=readInt();
}
initialize(N,A,B);
std::vector<int> res(Q);
for(int j=0;j<Q;j++)
{
if(T[j]==1) res[j]=cat(V[j]);
else if(T[j]==2) res[j]=dog(V[j]);
else res[j]=neighbor(V[j]);
}
for(int j=0;j<Q;j++)
printf("%d\n",res[j]);
// for (int x = 1; x <= N; x++)
// cerr << x << ' ' << chain[x] << ' ' << head[chain[x]] << ' ' << tail[chain[x]] << '\n';
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
