Gọi các đỉnh bị chặn là đỉnh đen, các đỉnh không bị chặn là đỉnh trắng

Nhận xét 1: Mọi đỉnh trên cây đều có thể bị ảnh hưởng trừ đỉnh ~1~, đỉnh ~1~ có các con trực tiếp là: ~v_1~, ~v_2~, ~v_3~, ~\dots~, ~v_k~. Cây con gốc ~v_1, v_2, v_3, \dots, v_k~ gọi là các nhánh của cây con gốc ~1~. Giả sử như xóa ~1~ cạnh ở một nhánh bất kỳ, thì các đỉnh thuộc nhánh đó bao gồm cả đỉnh đen đều không thể đến được đỉnh ~1~ ( vì tất cả các cạnh trên cây đều là cầu ). Vì vậy, khi tìm số cạnh cần xóa là ít nhất, mỗi nhánh chỉ cần xóa nhiều nhất ~1~ cạnh và điều kiện để thực hiện xóa cạnh trên nhánh chính là trong nhánh phải có ít nhất ~1~ đỉnh đen.

Nhận xét 2: Khi đã xác định được số cạnh cần xóa là ít nhất, ta phải xác định được số đỉnh trắng mà sau khi xóa cạnh đi là ít nhất có thể. Ta thấy rằng thao tác xóa đi một cạnh ~(u,v)~ với ~u~ là cha của ~v~ chính là tách cây con gốc ~v~ ra khỏi cây con chứa gốc ~u~, mà cây con chứa gốc ~u~ này có gốc là đỉnh ~1~. Vậy số đỉnh trắng và đỉnh đen phải chắc chắn nằm trong hết cây con gốc ~v~ này.

Nhận xét 3: Để số đỉnh trắng và đỉnh đen nằm gọn trong cây con gốc ~v~, ta phải chọn đỉnh ~v~ là tổ tiên của mọi đỉnh trắng và đỉnh đen trong nhánh đang xét và để tối ưu số đỉnh trắng và đỉnh đen là ít nhất thì đỉnh ~v~ phải xa đỉnh ~1~ nhất, nói cách khác chính là tổ tiên chung gần nhất của các đỉnh trắng và đỉnh đen.

Thuật toán

• Xem các đỉnh trên cây là một phần tử trong mảng, ta sẽ lần lượt đánh số các đỉnh trên cây bằng Euler Tour.
• Duy trì một Set để quản lý các đỉnh đen ở trong nhánh, Set này chứa các phần tử là thứ tự đánh số của đỉnh bằng Euler Tour.
• Từ Nhận xét 3, ta thấy tìm LCA của một tập đỉnh chính là đỉnh có số thứ tự nhỏ nhất được đánh số bằng Euler Tour trong tập đỉnh đó và lấy đỉnh có số thứ tự lớn nhất được đánh số bằng Euler Tour trong cùng tập đỉnh đang xét. Vậy áp dụng Nhận xét 3, ta thực hiện tìm LCA của các đỉnh trắng và đỉnh đen bằng cách lấy phần tử nhỏ nhất trong Set ( đỉnh có số thứ tự nhỏ nhất ) và lấy phần tử lớn nhất trong Set ( đỉnh có số thứ tự lớn nhất ).
• Để tính số cạnh tối ưu, như ở Nhận xét 1, nếu nhánh hiện tại đang xét có ít nhất ~1~ đỉnh đen thì tăng đáp án lên ~1~.
• Để tính số đỉnh trắng, ta thấy sau khi có đỉnh ~v~ tối ưu, ta sẽ tính số đỉnh trắng bằng cách lấy tổng số đỉnh thuộc cây con gốc ~v~ trừ đi số đỉnh đen.

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int LOG = 20;
const int N = 4E5;

vector<int> adj[N+9];
int par[N+9][LOG+9], sz[N+9], nodes[N+9], pos[N+9], branch[N+9], high[N+9];
int n, q;
int cnt = 0;
set<int> branchNodes[N+9];
int ansRoads = 0, ansBlocked = 0, treeSize = 0;
int curLCA[N+9];

void DFS(int u,int p,int top)
{
    sz[u] = 1;
    nodes[u] = ++cnt;
    pos[cnt] = u;
    branch[u] = top;

    for (int i = 0;i < (int)adj[u].size(); ++i)
    {
        int v = adj[u][i];
        if (v == p) continue;
        high[v] = high[u] + 1;
        par[v][0] = u;
        DFS(v, u, top);
        sz[u] += sz[v];
    }
}

void initLCA()
{
    for (int j = 1;j <= LOG; ++j)
        for (int u = 1;u <= n; ++u)
            par[u][j] = par[par[u][j-1]][j-1];
}

int LCA(int u,int v)
{
    if (high[u] < high[v]) swap(u,v);

    for (int j = LOG;j >= 0; --j)
        if (high[par[u][j]] >= high[v]) u = par[u][j];

    if (u == v) return u;

    for (int j = LOG;j >= 0; --j)
        if (par[u][j] != par[v][j])
        {
            u = par[u][j];
            v = par[v][j];
        }

return par[u][0];
}

int setLCA(const set<int> &s)
{
    if (s.empty()) return 0;

    set<int>::iterator it = s.begin();
    int smallNode = pos[*it];

    it = s.end(); --it;
    int bigNode = pos[*it];

return LCA(smallNode, bigNode);
}

void addNode(int node)
{
    int topNode = branch[node];
    if (branchNodes[topNode].empty()) ++ansRoads;

    branchNodes[topNode].insert(nodes[node]);

    int newLCA = setLCA(branchNodes[topNode]);

    ansBlocked++;

    treeSize += sz[newLCA] - sz[curLCA[topNode]];
    curLCA[topNode] = newLCA;
}

void delNode(int node)
{
    int topNode = branch[node];
    branchNodes[topNode].erase(nodes[node]);

    if (branchNodes[topNode].empty()) --ansRoads;

    int newLCA = setLCA(branchNodes[topNode]);
    ansBlocked--;

    treeSize += sz[newLCA] - sz[curLCA[topNode]];
    curLCA[topNode] = newLCA;
}


int main()
{
    fastIO

    cin>>n>>q;

    for (int i = 2;i <= n; ++i)
    {
        int p;
        cin>>p;
        adj[p].push_back(i);
        adj[i].push_back(p);
    }

    high[0] = -1;
    for (int i = 0;i < (int)adj[1].size(); ++i)
    {
        int u = adj[1][i];
        high[u] = 1;
        DFS(u, 1, u);
        sz[1] += sz[u];
    }

    initLCA();
    while (q--)
    {
        string c;
        int node;
        cin>>c>>node;
        if (c == "freeze") addNode(node);
        if (c == "unfreeze") delNode(node);

        cout<<ansRoads<<" "<<treeSize - ansBlocked<<"\n";
    }
}