C++17里面的匿名函数

自身调用可以这么写：

function<int(int x)> dfs = [&](int x) {
    if(!x) return 0;
    return dfs(x - 1);
};

这么写是不行的，（可能）因为 auto 无法和 dfs(x - 1) 匹配

auto dfs = [&](int x) {
    if(!x) return 0;
    return dfs(x - 1);
};
// error: use of 'dfs' before deduction of 'auto'

---

来自于 ycs 的神仙做法

template <typename F> struct Y_Combinator {
    Y_Combinator(F f) : _f(f) { }
    template <typename... Args> auto operator()(Args &&... t) const {
        return _f(*this, std::forward<Args>(t)...);
    }
    F _f;
};
template <typename F> Y_Combinator<F> Y(F &&f) {
    return Y_Combinator<F>(forward<F>(f));
}

---

比如说线段树：

Y([&](auto self, int rt, int l, int r) -> void {
    L[rt] = l, R[rt] = r;
    if (l == r) {
        sum[rt] = a[l];
    } else {
        int mid = (l + r) / 2;
        self(rt * 2, l, mid);
        self(rt * 2 + 1, mid + 1, r);
        [&](int rt) -> void {
            sum[rt] = sum[rt * 2] + sum[rt * 2 + 1];
        } (rt);
    }
}) (1, 1, n);

---

重灾区 https://loj.ac/p/6683

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

const int mod = 998244353;

int n, m, q;

inline void upd(ll &x, ll y) {
    (x += y) >= mod ? x -= mod : 0;
}

inline void upd(int &x, ll y) {
    (x += y) >= mod ? x -= mod : 0;
}

inline int mul(int x, int y) {
    int ret; __asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n":"=d"(ret):"a"(x),"b"(y),"c"(mod));
    return ret;
};

template <typename F> struct Y_Combinator {
    Y_Combinator(F f) : _f(f) { }
    template <typename... Args> auto operator()(Args &&... t) const {
        return _f(*this, std::forward<Args>(t)...);
    }
    F _f;
};
template <typename F> Y_Combinator<F> Y(F &&f) {
    return Y_Combinator<F>(forward<F>(f));
}


struct FastIO {
    static const int S = 1e7;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar() {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        return buf[pos++];
    }
    inline int operator () () {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline ll operator ! () {
        int c = xchar(); ll x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline void wchar(int x) {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos++] = x;
    }
    inline void operator () (ll x) {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
        wchar('\n');
    }
    inline void space(ll x) {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
        wchar(' ');
    }
    inline void nextline() {
        wchar('\n');
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;

struct YFS {

    #define N int(5e6 + 10)

    int n, m, w[N];

    vector<pair<int, int> > res_eds;
    vector<pair<int, int> > E;
    vector<vector<int> > g;

    int head[N], rest[N], to[N], tot;
    void add(int u, int v) {
        to[++ tot] = v, rest[tot] = head[u], head[u] = tot;
    }

    int sta[N], dfn[N], low[N], clk, cnt, cat[N];
    void tarj(int u, int fa) {
        cat[u] = 1;
        static int top = 0;
        dfn[u] = low[u] = ++ clk, sta[++ top] = u;
        for(int i = head[u] ; i ; i = rest[i]) {
            int v = to[i];
            if(!dfn[v]) {
                tarj(v, u);
                low[u] = min(low[u], low[v]);
                if(low[v] >= dfn[u]) {
                    ++ cnt;
                    E.push_back(make_pair(u, cnt));
                    int neko;
                    do {
                        neko = sta[top --];
                        E.push_back(make_pair(neko, cnt));
                    } while(neko != v);
                }
            } else if(v != fa) {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }

    int fa[N], dep[N];

    int rt;

    void initgraph() {
        for(int i = 1 ; i <= n ; ++ i) {
            w[i] = io();
        }
        for(int i = 1 ; i <= m ; ++ i) {
            int u = io(), v = io();
            add(u, v), add(v, u);
        }
        cnt = n;
        tarj(1, 0);
        for(int i = 1 ; i <= n ; ++ i) head[i] = 0; tot = 0;
        for(int i = 0, u, v ; i < E.size() ; ++ i) add(u = E[i].first, v = E[i].second), add(v, u);

        Y([&] (auto self, int u, int tfa) -> void {
        	if(!cat[u]) w[u] = 0x3f3f3f3f;
            for(int i = head[u] ; i ; i = rest[i]) {
                int v = to[i];
                if(v == tfa) continue;
                self(v, u);
                if(!cat[u]) w[u] = min(w[u], w[v]);
            }
            if(!cat[u] && tfa) w[u] = min(w[u], w[tfa]);
        }) (1, 0);


        n = cnt;

        vector<int> ids;
        for(int i = 1 ; i <= n ; ++ i) {
            ids.emplace_back(i);
        }
        sort(ids.begin(), ids.end(), [&] (int i, int j) {
            return w[i] > w[j];
        });
        vector<int> acc(n + 5), vis(n + 5);
        for(int i = 1 ; i <= n ; ++ i) {
            acc[i] = i;
        }

        g = vector<vector<int> > (n + 5, vector<int> ());
        [&] (auto get) {
	        for(const int &u: ids) {
	            vis[u] = 1;
	            for(int i = head[u] ; i ; i = rest[i]) {
	                int v = to[i];
	                if(vis[v]) {
	                    g[u].emplace_back(get(v));
	                    assert(u == acc[u]); // must be true
	                    acc[get(v)] = u;
	                }
	            }
	            rt = u; // 最后一个就是根了
	        }
	    } ( Y([&] (auto get, int x) -> int { return x == acc[x] ? x : acc[x] = get(acc[x]); }) );


        Y([&] (auto self, int u) -> void {
        	int lst = u;
                for(const int &v: g[u]) {
                    int nxt = ++ n;
                    w[n] = w[u];
                    res_eds.emplace_back(lst, nxt);
                    res_eds.emplace_back(nxt, v);
                    lst = nxt;
                    self(v);
                }
        }) (rt);

        g = vector<vector<int> > (n + 5, vector<int> ());
        for(const auto &e: res_eds) {
            g[e.first].emplace_back(e.second);
            g[e.second].emplace_back(e.first);
        }
    }

    #undef N
} A, B;

int main() {
    n = io(), m = io();

    A.n = n, A.m = m;
    A.initgraph();
    B.n = n, B.m = m;
    B.initgraph();

    int bakn = n;
    n = A.n;
    // printf("n = %d\n", n);
    vector<int> head(n + 5), rest(2 * n + 5), to(2 * n + 5);

    int tot = 1;
    for(const auto &e: A.res_eds) {
        int u, v; tie(u, v) = e;
        auto add = [&] (int u, int v) {
            to[++ tot] = v, rest[tot] = head[u], head[u] = tot;
        };
        add(u, v), add(v, u);
    }

    vector<int> ban(2 * n + 5); // 边分治的ban掉的边
    vector<vector<int> > ch(30 * n + 5, vector<int> (2)); // 边分树上每个节点
    vector<int> hd(n + 5); // 边分树每个点的根
    vector<int> dn(n + 5); // 边分树每个点的最底端
    vector<int> tval(30 * n + 5); // 边分树每个点的权值
    vector<int> tsz(30 * n + 5); // 边分树每个点的子树大小
    vector<int> edup(n + 5); // 每个点从哪条边来的
    vector<int> tag(n + 5); // 分治中心的时候记录一下上面的点

    // exit(0);

    int spl_cnt = 0;
    [&] () {
        vector<int> sz(n + 5);
        int size, root, mxrot;
        vector<int> dep(n + 5), tfa(n + 5);

        for(int i = 1 ; i <= n ; ++ i) {
            hd[i] = ++ spl_cnt;
            dn[i] = hd[i];
        }

        Y([&] (auto self, int u, int fa) -> void {
            tfa[u] = fa;
            dep[u] = dep[fa] + 1;
            for(int i = head[u] ; i ; i = rest[i]) {
                int v = to[i];
                if(v != fa) {
                    self(v, u);
                    edup[v] = i;
                }
            };
            // 有根树
        }) (A.rt, 0);

        mxrot = 0x3f3f3f3f, root = 0, size = n;
        Y([&] (auto self, int u, int fa) -> void {
        	sz[u] = 1;
            for(int i = head[u] ; i ; i = rest[i]) {
                int v = to[i];
                if(!ban[i] && v != fa) {
                    self(v, u);
                    sz[u] += sz[v];
                    int val = max(sz[v], size - sz[v]);
                    if(val <= mxrot) {
                        mxrot = val;
                        root = i;
                    }
                }
            }
        }) (1, 0);

        Y([&] (auto self, int e, auto getsz) -> void {
        	if(!e) {
                return ;
            }
            ban[e] = ban[e ^ 1] = 1;
            int u = to[e], v = to[e ^ 1];
            if(dep[u] > dep[v]) {
                swap(u, v);
            }
            [&] (int x) {
            	Y([&] (auto self, int u, int fa, int mxval) -> void {
            		if(tag[u]) mxval = A.w[u];
                    [&] (int x) {
                        ch[dn[x]][0] = ++ spl_cnt;
                        dn[x] = ch[dn[x]][0];
                        if(x <= bakn) {
                            tsz[spl_cnt] = 1;
                            tval[spl_cnt] = mxval;
                        }
                    } (u);
                    for(int i = head[u] ; i ; i = rest[i]) {
                        int v = to[i];
                        if(!ban[i] && v != fa) {
                            self(v, u, mxval);
                        }
                    }
            	}) (x, 0, 0);
            } ([&] (int x, int vls) {
                while(x) {
                    tag[x] = vls;
                    if(!tfa[x] || ban[edup[x]]) {
                        return x;
                    }
                    x = tfa[x];
                }
                assert(0);
                return -1;
            } (u, 1));

            [&] (int x, int vls) {
                while(x) {
                    tag[x] = vls;
                    if(!tfa[x] || ban[edup[x]]) {
                        break;
                    }
                    x = tfa[x];
                }
            } (u, 0);

            [&] (int x) {
            	Y([&] (auto self, int u, int fa) -> void {
            		([&] (int x) {
                        ch[dn[x]][1] = ++ spl_cnt, dn[x] = ch[dn[x]][1];
                        if(x <= bakn) tsz[spl_cnt] = 1;
                    }) (u);
                    for(int i = head[u] ; i ; i = rest[i]) {
                        int v = to[i];
                        if(!ban[i] && v != fa) self(v, u);
                    }
            	}) (x, 0);
            } (v);

            vector<tuple<int, int> > nxt;
            nxt.emplace_back(to[e], sz[to[e]]);
            nxt.emplace_back(to[e ^ 1], size - sz[to[e]]);
            for(const auto &nt: nxt) {
                int v; tie(v, size) = nt;
                mxrot = 0x3f3f3f3f, root = 0;
                getsz(v, 0), self(root, getsz);
            }
        } ) (root, Y([&] (auto self, int u, int fa) -> void {
        	sz[u] = 1;
            for(int i = head[u] ; i ; i = rest[i]) {
                int v = to[i];
                if(!ban[i] && v != fa) {
                    self(v, u);
                    sz[u] += sz[v];
                    int val = max(sz[v], size - sz[v]);
                    if(val <= mxrot) {
                        mxrot = val;
                        root = i;
                    }
                }
            }
        }));
    } ();

    [&] () {
        ll ans = 0;
        auto g = B.g;
        Y([&] (auto self, int u, int fa) -> int {
        	int res = u <= bakn ? hd[u] : 0;
            ll coef = 0;

            [&] (auto merge) {
	            for(const int &v: g[u]) {
	                if(v != fa) {
	                    int ndv = self(v, u);
	                    coef = 0;
	                    res = merge(res, ndv);
	                    upd(ans, mul(coef, B.w[u]));
	                }
	            }
	        } (Y([&] (auto self, int x, int y) -> int {
            	if(!x || !y) return x | y;
                upd(coef, mul(tval[ch[x][0]], tsz[ch[y][1]]) + mul(tval[ch[y][0]], tsz[ch[x][1]]));
                upd(tval[x], tval[y]);
                tsz[x] += tsz[y];
                ch[x][0] = self(ch[x][0], ch[y][0]);
                ch[x][1] = self(ch[x][1], ch[y][1]);
                return x;
            }));
            return res;
        }) (B.rt, 0);
        io(ans);
    } ();
}