基环树

There is considerable debate over how we should react if we detect a signal from an alien civilisation.
— IELTS

基环树，是基于环的树，基环树分为两类：无向和有向。

无向基环树特征：个点条边的连通图。一个环，换上挂着很多子树。

有向基环树特征：个点每个点一条出边。往往不只是一棵树，是一个森林。每个树有一个环。

无向基环树

https://atcoder.jp/contests/abc266/tasks/abc266_f

给一个无向基环树，次询问，每次询问查询两个点之间是否存在唯一的简单路径。

思路：等价于询问两个点是否属于同一个子树。先拓扑排序，每次删除叶子（入度为）。没有入过队列的就是环上的点，（环上的点度数都为）。再给环上的点打上不一样的标记，并把挂在该点上的子树打上一样的标记。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 200007
vector<int> e[N];
int deg[N], vis[N], bl[N], col;
queue<int> q;

void dfs(int u, int fa) {
    for (auto v : e[u])
        if (v != fa && !bl[v]) {
            bl[v] = bl[u]; dfs(v, u);
        }
}

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        int u = rd(), v = rd();
        e[u].pb(v); e[v].pb(u);
        ++deg[u]; ++deg[v];
    }
    for (int i = 1; i <= n; ++i)
        if (deg[i] == 1) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = 1;
        for (auto v : e[u]) {
            --deg[v];
            if (deg[v] == 1) q.push(v);
        }
    }
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) bl[i] = ++col;
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) dfs(i, i);
    for (int q = rd(); q; --q) {
        int u = rd(), v = rd();
        puts(bl[u] == bl[v] ? "Yes" : "No");
    }
    return 0;
}

有向基环树

https://codeforces.com/gym/393017/problem/B

思路：注意到，首先，每个点最多只会操作一次；其次，最后的复读值一定出现在每个环里。拓扑排序，找出环。统计该环里出现过的复读值，对这些复读值的计数器 +1 ，再枚举可能的最后的复读值，更新答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 1000007
int a[N], b[N], indeg[N], vis[N], cnt;
vector<int> e[N];
queue<int> q;
map<int, int> m, m0; // val cnt
set<int> s;

void dfs(int u) {
    vis[u] = 1; s.insert(a[u]);
    for (auto v : e[u]) {
        if (!vis[v]) dfs(v);
    }
}

inline void work() {
    int n = rd(); m.clear(); m0.clear(); cnt = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); vis[i] = 0; indeg[i] = 0; e[i].clear();
        m0[a[i]]++;
    }
    for (int i = 1; i <= n; ++i) {
        b[i] = rd(); e[i].pb(b[i]); ++indeg[b[i]];
    }
    for (int i = 1; i <= n; ++i)
        if (!indeg[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = 1;
        for (auto v : e[u]) {
            --indeg[v];
            if (!indeg[v]) q.push(v);
        }
    }
    int ans = 1e7;
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) {
            ++cnt; dfs(i);
            for (auto val : s) m[val]++;
            s.clear();
        }
    for (auto node : m) {
        int val = node.first, cntt = node.second;
        if (cntt != cnt) continue;
        ans = min(ans, n - m0[val]);
    }
    if (ans == 1e7) puts("-1");
    else printf("%d\n", ans);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}