支配树

发表于 2019-07-29 更新于 2023-12-05 分类于树阅读次数：

定义

semi[x] 半必经点： $x$ 的祖先 $z$ 中，能不经过 $z$ 和 $x$ 之间的树上的点而到达 $x$ 的点中深度最小的。
idom[x] 最近必经点：就是深度最大的根到 $x$ 的必经点。

其它的证明看不懂 T^T。

模板

vector<int> G[maxn], rG[maxn];
vector<int> dt[maxn];
// 原图，反图，支配树

namespace DomTree {
    int fa[maxn], idx[maxn], tot, ridx[maxn];
    int c[maxn], best[maxn], semi[maxn], idom[maxn];
    void clear(int n) {
        tot = 0;
        fill(c, c + n + 1, -1);
        fill(idx, idx + n + 1, 0);
        for (int i = 0; i <= n; i++) {
            dt[i].clear();
            semi[i] = best[i] = i;
        }
    }
    void dfs(int u) {
        idx[u] = ++tot; ridx[tot] = u;
        for (int& v: G[u]) {
            if (idx[v]) continue;
            fa[v] = u; dfs(v);
        }
    }
    int fix(int x) {
        if (c[x] == -1) return x;
        int &f = c[x], rt = fix(f);
        if (idx[semi[best[x]]] > idx[semi[best[f]]]) best[x] = best[f];
        return f = rt;
    }
    void build(int rt) {
        dfs(rt);
        for (int i = tot; i >= 1; i--) {
            int x = ridx[i], mn = tot + 1;
            for (int& u: rG[x]) {
                if (!idx[u]) continue;
                fix(u); mn = min(mn, idx[semi[best[u]]]);
            }
            c[x] = fa[x];
            dt[semi[x] = ridx[mn]].push_back(x);
            x = ridx[i - 1];
            for (int& u: dt[x]) {
                fix(u);
                if (semi[best[u]] != x) idom[u] = best[u];
                else idom[u] = x;
            }
            dt[x].clear();
        }
        for (int i = 2; i <= tot; i++) {
            int u = ridx[i];
            if (idom[u] != semi[u]) idom[u] = idom[idom[u]];
            dt[idom[u]].push_back(u);
        }
    }
}

阅读全文 »

2019牛客暑期多校训练营第 4 场

发表于 2019-07-28 更新于 2023-12-05 分类于训练，牛客多校阅读次数：

rank	solved	A	B	C	D	E	F	G	H	I	J	K
62	7	O	Ø	O	O	.	.	.	.	O	O	O

阅读全文 »

回文树

发表于 2019-07-26 更新于 2023-12-05 分类于字符串，后缀自动机阅读次数：

模板

namespace pam {
    int sz, tot, last;
    int ch[maxn][26], len[maxn], fail[maxn];
    int cnt[maxn], dep[maxn];
    char s[maxn];
    int node(int l) {
        sz++; ms(ch[sz], 0);
        len[sz] = l; fail[sz] = cnt[sz] = dep[sz] = 0;
        return sz;
    }
    void clear() {
        sz = -1; last = 0;
        s[tot = 0] = '$';
        node(0); node(-1);
        fail[0] = 1;
    }
    int getfail(int x) {
        while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
        return x;
    }
    void insert(char c) {
        s[++tot] = c;
        int now = getfail(last);
        if (!ch[now][c - 'a']) {
            int x = node(len[now] + 2);
            fail[x] = ch[getfail(fail[now])][c - 'a'];
            dep[x] = dep[fail[x]] + 1;
            ch[now][c - 'a'] = x;
        }
        last = ch[now][c - 'a'];
        cnt[last]++;
    }
    void count() {
        for (int i = sz; i >= 0; i--) {
            cnt[fail[i]] += cnt[i];
        }
    }
}