Submission #59382938

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef LOCAL
#pragma GCC optimize("Ofast", "unroll-loops")
#endif
#include <bits/stdc++.h>
#include <unistd.h>
#define FASTIO
namespace mitsuha::io {
#define READ_INTEGRAL(type_t) void rd(type_t &x) { rd_integer(x); }
#define READ_FLOATING(type_t) void rd(type_t &x) { rd_real(x); }
#define WRITE_INTEGRAL(type_t) void wt(type_t x) { wt_integer(x); }
#define WRITE_FLOATING(type_t) void wt(type_t x) { wt_real(x); }
static constexpr uint32_t SZ = 1 << 17;
char input_buffer[SZ];
char output_buffer[SZ];
char out[100];
uint32_t pil = 0, pir = 0, por = 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifndef LOCAL
#pragma GCC optimize("Ofast", "unroll-loops")
#endif

#include <bits/stdc++.h>

#include <unistd.h>

#define FASTIO
namespace mitsuha::io {
#define READ_INTEGRAL(type_t) void rd(type_t &x) { rd_integer(x); }
#define READ_FLOATING(type_t) void rd(type_t &x) { rd_real(x); }
#define WRITE_INTEGRAL(type_t) void wt(type_t x) { wt_integer(x); }
#define WRITE_FLOATING(type_t) void wt(type_t x) { wt_real(x); }

static constexpr uint32_t SZ = 1 << 17;
char input_buffer[SZ];
char output_buffer[SZ];
char out[100];
uint32_t pil = 0, pir = 0, por = 0;

struct Pre {
    char num[10000][4];
    constexpr Pre() : num() {
        for (int i = 0; i < 10000; i++) {
            for (int j = 3, n = i; j >= 0; j--, n /= 10) {
                num[i][j] = n % 10 | '0';
            }
        }
    }
} constexpr pre;

inline void load() {
    memcpy(input_buffer, input_buffer + pil, pir - pil);
    pir = pir - pil + fread(input_buffer + pir - pil, 1, SZ - pir + pil, stdin);
    pil = 0;
    if (pir < SZ) input_buffer[pir++] = '\n';
}
inline void flush() {
    fwrite(output_buffer, 1, por, stdout);
    por = 0;
}
void rd(char &c) { 
    do { 
        if (pil >= pir) load(); 
        c = input_buffer[pil++]; 
    } while (isspace(c));
}
void rd(std::string &x) {
    x.clear();
    char c;
    do { 
        if (pil >= pir) load(); 
        c = input_buffer[pil++]; 
    } while (isspace(c));
    do {
        x += c;
        if (pil == pir) load();
        c = input_buffer[pil++];
    } while (!isspace(c));
}
template<typename T>
void rd_real(T &x) {
    std::string s;
    rd(s);
    x = stod(s);
}
template<typename T>
void rd_integer(T &x) {
    if (pil + 100 > pir) load();
    char c;
    do c = input_buffer[pil++]; while (c < '-');
    bool minus = 0;
    if constexpr (std::is_signed<T>::value or std::is_same_v <T, __int128 >) {
        if (c == '-') {
            minus = 1;
            c = input_buffer[pil++];
        }
    }
    x = 0;
    while ('0' <= c) { x = x * 10 + (c & 15), c = input_buffer[pil++]; }
    if constexpr (std::is_signed<T>::value or std::is_same_v < T, __int128 >) {
        if (minus) x = -x;
    }
}

READ_INTEGRAL(int) 
READ_INTEGRAL(long int)
READ_INTEGRAL(long long)
READ_INTEGRAL(__int128)
READ_INTEGRAL(unsigned int)
READ_INTEGRAL(unsigned long long)
READ_INTEGRAL(unsigned __int128)
READ_FLOATING(double)
READ_FLOATING(long double)
READ_FLOATING(__float128)

template<class T, class U> void rd(std::pair <T, U> &p) {
    rd(p.first);
    rd(p.second);
}
template<size_t N = 0, typename T> void rd_tuple(T &t) {
    if constexpr (N < std::tuple_size<T>::value) {
        auto &x = std::get<N>(t);
        rd(x);
        rd_tuple<N + 1>(t);
    }
}
template<class... T> void rd(std::tuple<T...> &tpl) {
    rd_tuple(tpl);
}
template<size_t N = 0, typename T> void rd(std::array <T, N> &x) {
    for (auto &d: x) rd(d);
}
template<class T> void rd(std::vector <T> &x) {
    for (auto &d: x) rd(d);
}

void read() {}
template<class Head, class... Args>
void read(Head &h, Args &... t) {
    rd(h);
    read(t...);
}

void wt(const char c) {
    if (por == SZ) flush();
    output_buffer[por++] = c;
}
void wt(const std::string &s) {
    for (char c: s) wt(c);
}
void wt(const char *s) {
    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++) wt(s[i]);
}
template<typename T>
void wt_integer(T x) {
    if (por > SZ - 100) flush();
    if (x < 0) { output_buffer[por++] = '-', x = -x; }
    int outi;
    for (outi = 96; x >= 10000; outi -= 4, x /= 10000) {
        memcpy(out + outi, pre.num[x % 10000], 4);
    }
    if (x >= 1000) {
        memcpy(output_buffer + por, pre.num[x], 4);
        por += 4;
    }
    else if (x >= 100) {
        memcpy(output_buffer + por, pre.num[x] + 1, 3);
        por += 3;
    }
    else if (x >= 10) {
        int q = (x * 103) >> 10;
        output_buffer[por] = q | '0';
        output_buffer[por + 1] = (x - q * 10) | '0';
        por += 2;
    }
    else output_buffer[por++] = x | '0';
    memcpy(output_buffer + por, out + outi + 4, 96 - outi);
    por += 96 - outi;
}
template<typename T>
void wt_real(T x) {
    std::ostringstream oss;
    oss << std::fixed << std::setprecision(15) << double(x);
    std::string s = oss.str();
    wt(s);
}

WRITE_INTEGRAL(int)
WRITE_INTEGRAL(long int)
WRITE_INTEGRAL(long long)
WRITE_INTEGRAL(__int128)
WRITE_INTEGRAL(unsigned int)
WRITE_INTEGRAL(unsigned long long)
WRITE_INTEGRAL(unsigned __int128)
WRITE_FLOATING(double)
WRITE_FLOATING(long double)
WRITE_FLOATING(__float128)

template<class T, class U>
void wt(const std::pair <T, U> val) {
    wt(val.first);
    wt(' ');
    wt(val.second);
}
template<size_t N = 0, typename T>
void wt_tuple(const T t) {
    if constexpr (N < std::tuple_size<T>::value) {
        if constexpr (N > 0) { wt(' '); }
        const auto x = std::get<N>(t);
        wt(x);
        wt_tuple<N + 1>(t);
    }
}
template<class... T> void wt(std::tuple<T...> tpl) {
    wt_tuple(tpl);
}
template<class T, size_t S> void wt(const std::array <T, S> val) {
    for (size_t i = 0, n = val.size(); i < n; i++) {
        if (i) wt(' ');
        wt(val[i]);
    }
}
template<class T> void wt(const std::vector<T> val) {
    for (size_t i = 0, n = val.size(); i < n; i++) {
        if (i) wt(' ');
        wt(val[i]);
    }
}

void print() { wt('\n'); }
template<class Head, class... Args>
void print(Head &&head, Args &&... args) {
    wt(head);
    if (sizeof...(Args)) wt(' ');
    print(std::forward<Args>(args)...);
}

void __attribute__((destructor)) _d() {
    flush(); 
}
} // namespace mitsuha::io

namespace mitsuha {
    using io::read; using io::print; using io::flush;
}

namespace mitsuha {
template <class T> bool chmin(T& x, const T& y) { 
    return y >= x ? false : (x = y, true); 
}
template <class T> bool chmax(T& x, const T& y) { 
    return y <= x ? false : (x = y, true); 
}
template <class T> constexpr T fld(const T x, const T y) { 
    T q = x / y, r = x % y; return q - ((x ^ y) < 0 and (r != 0)); 
}
template <class T> constexpr T cld(const T x, const T y) { 
    T q = x / y, r = x % y; return q + ((x ^ y) > 0 and (r != 0)); 
}
template <class T> constexpr T rem(const T x, const T y) { 
    return x - y * fld(x, y); 
}
template <class Iterable> void settify(Iterable& a) { 
    std::sort(a.begin(), a.end()), a.erase(std::unique(a.begin(), a.end()), a.end()); 
}
template <typename T, typename... Vectors>
void concat(std::vector<T> &first, const Vectors &... others) {
    std::vector<T> &res = first;
    (res.insert(res.end(), others.begin(), others.end()), ...);
}
template<typename T>
std::map<T, int> Counter(std::vector<T> &a){
    std::map<T, int> cnt;
    for (auto &x: a) ++cnt[x];
    return cnt;
}
template <size_t D> struct Dim : std::array<int, D> {
    template <typename ...Ints> Dim(const Ints& ...ns) : 
        std::array<int, D>::array{ static_cast<int>(ns)... } {}
};
template <typename ...Ints> Dim(const Ints& ...) -> Dim<sizeof...(Ints)>;
template <class T, size_t D, size_t I = 0>
auto ndvec(const Dim<D> &ns, const T& value = {}) {
    if constexpr (I + 1 < D) {
        return std::vector(ns[I], ndvec<T, D, I + 1>(ns, value));
    } else {
        return std::vector<T>(ns[I], value);
    }
}
}

namespace mitsuha {
using str = std::string;
using int128 = __int128;
using uint128 = unsigned __int128;
template <class T> using min_priority_queue 
                            = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T> using max_priority_queue 
                            = std::priority_queue<T, std::vector<T>, std::less<T>>;
}
namespace mitsuha { 
    const std::vector<std::string> Yes = {"No", "Yes"};
    const std::vector<std::string> YES = {"NO", "YES"};
}
 
#ifndef __COUNTER__
#define __COUNTER__ __LINE__
#endif

#define TL (long long)

#define OVERLOAD5(a, b, c, d, e, ...) e
#define REP1_0(b, c) REP1_1(b, c)
#define REP1_1(b, c) for (long long REP_COUNTER_##c = 0; REP_COUNTER_##c < TL(b); ++REP_COUNTER_##c)
#define REP1(b) REP1_0(b, __COUNTER__)
#define REP2(i, b) for (long long i = 0; i < TL(b); ++i)
#define REP3(i, a, b) for (long long i = TL(a); i < TL(b); ++i)
#define REP4(i, a, b, c) for (long long i = TL(a); i < TL(b); i += TL(c))
#define For(...) OVERLOAD5(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define RREP2(i, a) for (long long i = TL(a)-1; i >= 0; --i)
#define RREP3(i, a, b) for (long long i = TL(b)-1; i >= TL(a); --i)
#define RREP4(i, a, b, c) for (long long i = TL(b)-1; i >= TL(a); i -= TL(c))
#define Frr(...) OVERLOAD5(__VA_ARGS__, RREP4, RREP3, RREP2)(__VA_ARGS__)

#define Int(...) int __VA_ARGS__; read(__VA_ARGS__)
#define Ll(...) long long __VA_ARGS__; read(__VA_ARGS__)
#define Dbl(...) double __VA_ARGS__; read(__VA_ARGS__)
#define Chr(...) char __VA_ARGS__; read(__VA_ARGS__)
#define Str(...) string __VA_ARGS__; read(__VA_ARGS__)
#define Vt(type, name, size) vector<type> name(size); read(name)
#define Vvt(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); read(name)
#define die_int(...) do { print(__VA_ARGS__); return; } while (false)
#define die_ext(...) do { print(__VA_ARGS__); return 0; } while (false)

#define All(iterable) std::begin(iterable), std::end(iterable)
#define len(iterable) TL iterable.size()
#define elif else if

#define KBIT(a, k) ((a >> k) & 1)

using namespace mitsuha;
using namespace std;

#ifdef LOCAL
#define  debug_path "library/debug/pprint.hpp"
#include debug_path
#define Assert(x) assert(x)
#else
#define debug(...) void(0)
#define debug2(...) void(0)
#define debugbin(...) void(0)
#define Assert(x) void(0)
#endif
 
constexpr int iinf = std::numeric_limits<int>::max() / 2;
constexpr long long linf = std::numeric_limits<long long>::max() / 2;

namespace mitsuha{
template <typename T>
struct Edge {
    int frm, to;
    T cost;
    int id;
};

template <typename T = int, bool directed = false>
struct Graph {
    static constexpr bool is_directed = directed;
    int N, M;
    using cost_type = T;
    using edge_type = Edge<T>;
    vector<edge_type> edges;
    vector<int> indptr;
    vector<edge_type> csr_edges;
    vector<int> vc_deg, vc_indeg, vc_outdeg;
    bool prepared;

    class OutgoingEdges {
    public:
        OutgoingEdges(const Graph* G, int l, int r) : G(G), l(l), r(r) {}

        const edge_type* begin() const {
            if (l == r) { return 0; }
            return &G->csr_edges[l];
        }

        const edge_type* end() const {
            if (l == r) { return 0; }
            return &G->csr_edges[r];
        }

    private:
        const Graph* G;
        int l, r;
    };

    bool is_prepared() { return prepared; }

    Graph() : N(0), M(0), prepared(0) {}
    Graph(int N) : N(N), M(0), prepared(0) {}

    void build(int n) {
        N = n, M = 0;
        prepared = 0;
        edges.clear();
        indptr.clear();
        csr_edges.clear();
        vc_deg.clear();
        vc_indeg.clear();
        vc_outdeg.clear();
    }

    void add(int frm, int to, T cost = 1, int i = -1) {
        assert(!prepared);
        assert(0 <= frm && 0 <= to && to < N);
        if (i == -1) i = M;
        auto e = edge_type({frm, to, cost, i});
        edges.emplace_back(e);
        ++M;
    }

#ifdef FASTIO
    // wt, off
    void read_tree(bool wt = false, int off = 1) { read_graph(N - 1, wt, off); }

    void read_graph(int M, bool wt = false, int off = 1) {
        for (int m = 0; m < M; ++m) {
            int a, b;
            read(a, b);
            a -= off, b -= off;
            if (!wt) {
                add(a, b);
            } else {
                T c;
                read(c);
                add(a, b, c);
            }
        }
        build();
    }
#endif

    void build() {
        assert(!prepared);
        prepared = true;
        indptr.assign(N + 1, 0);
        for (auto&& e: edges) {
            indptr[e.frm + 1]++;
            if (!directed) indptr[e.to + 1]++;
        }
        for (int v = 0; v < N; ++v) { indptr[v + 1] += indptr[v]; }
        auto counter = indptr;
        csr_edges.resize(indptr.back() + 1);
        for (auto&& e: edges) {
            csr_edges[counter[e.frm]++] = e;
            if (!directed)
                csr_edges[counter[e.to]++] = edge_type({e.to, e.frm, e.cost, e.id});
        }
    }

    OutgoingEdges operator[](int v) const {
        assert(prepared);
        return {this, indptr[v], indptr[v + 1]};
    }

    vector<int> deg_array() {
        if (vc_deg.empty()) calc_deg();
        return vc_deg;
    }

    pair<vector<int>, vector<int>> deg_array_inout() {
        if (vc_indeg.empty()) calc_deg_inout();
        return {vc_indeg, vc_outdeg};
    }

    int deg(int v) {
        if (vc_deg.empty()) calc_deg();
        return vc_deg[v];
    }

    int in_deg(int v) {
        if (vc_indeg.empty()) calc_deg_inout();
        return vc_indeg[v];
    }

    int out_deg(int v) {
        if (vc_outdeg.empty()) calc_deg_inout();
        return vc_outdeg[v];
    }

    vector<int> new_idx;
    vector<bool> used_e;

    // vertex V[i] in G become i in the new graph
    // {G, es}
    // The amount of calculation is sum(deg(v)),
    // Be careful as it may be larger than n+m in the new graph
    Graph<T, directed> rearrange(vector<int> V, bool keep_eid = 0) {
        if (len(new_idx) != N) new_idx.assign(N, -1);
        int n = len(V);
        For(i, n) new_idx[V[i]] = i;
        Graph<T, directed> G(n);
        vector<int> history;
        For(i, n) {
            for (auto&& e: (*this)[V[i]]) {
                if (len(used_e) <= e.id) used_e.resize(e.id + 1);
                if (used_e[e.id]) continue;
                int a = e.frm, b = e.to;
                if (new_idx[a] != -1 && new_idx[b] != -1) {
                    history.emplace_back(e.id);
                    used_e[e.id] = 1;
                    int eid = (keep_eid ? e.id : -1);
                    G.add(new_idx[a], new_idx[b], e.cost, eid);
                }
            }
        }
        For(i, n) new_idx[V[i]] = -1;
        for (auto&& eid: history) used_e[eid] = 0;
        G.build();
        return G;
    }

    Graph<T, true> to_directed_tree(int root = -1, bool directed_away_from_root = true) {
        if (root == -1) root = 0;
        assert(!is_directed && prepared && M == N - 1);
        Graph<T, true> G1(N);
        vector<int> par(N, -1);
        auto dfs = [&](auto& dfs, int v) -> void {
            for (auto& e: (*this)[v]) {
                if (e.to == par[v]) continue;
                par[e.to] = v, dfs(dfs, e.to);
            }
        };
        dfs(dfs, root);
        for (auto& e: edges) {
            int a = e.frm, b = e.to;
            if (par[a] == b) swap(a, b);
            assert(par[b] == a);
            if (directed_away_from_root)
                G1.add(a, b, e.cost);
            else
                G1.add(b, a, e.cost);
        }
        G1.build();
        return G1;
    }

private:
    void calc_deg() {
        assert(vc_deg.empty());
        vc_deg.resize(N);
        for (auto&& e: edges) vc_deg[e.frm]++, vc_deg[e.to]++;
    }

    void calc_deg_inout() {
        assert(vc_indeg.empty());
        vc_indeg.resize(N);
        vc_outdeg.resize(N);
        for (auto&& e: edges) { vc_indeg[e.to]++, vc_outdeg[e.frm]++; }
    }
};

template<typename T, bool directed = false>
std::ostream &operator<<(std::ostream &out, const Graph<T, directed> &_G){
    auto G = _G;
    if (not G.prepared) {
        out << "frm to cost id";
        for (auto &&e: G.edges) 
            out << "\n" << e.frm << " " << e.to << " " << e.cost << " " << e.id;
    } else {
        out << "indptr ";
        for(const auto &value : G.indptr) {
            out << value << " ";
        }
        out << "\n";
        out << "frm to cost id";
        for(int v = 0; v < G.N; ++v) 
            for (auto &&e: G[v]) 
            out << "\n" << e.frm << " " << e.to << " " << e.cost << " " << e.id;
    }
    return out;
}
} // namespace mitsuha

namespace mitsuha{
template<typename GT>
struct Tree {
    using Graph_type = GT;
    GT &G;
    using WT = typename GT::cost_type;
    int N;
    vector<int> LID, RID, head, V, parent, VtoE;
    vector<int> depth;
    vector<WT> depth_weighted;

    Tree(GT &G, int r = 0, bool hld = 1) : G(G) { build(r, hld); }

    void build(int r = 0, bool hld = 1) {
        if (r == -1) return;
        N = G.N;
        LID.assign(N, -1), RID.assign(N, -1), head.assign(N, r);
        V.assign(N, -1), parent.assign(N, -1), VtoE.assign(N, -1);
        depth.assign(N, -1), depth_weighted.assign(N, 0);
        assert(G.is_prepared());
        int t1 = 0;
        dfs_sz(r, -1, hld);
        dfs_hld(r, t1);
    }

    void dfs_sz(int v, int p, bool hld) {
        auto &sz = RID;
        parent[v] = p;
        depth[v] = (p == -1 ? 0 : depth[p] + 1);
        sz[v] = 1;
        int l = G.indptr[v], r = G.indptr[v + 1];
        auto &csr = G.csr_edges;
        for (int i = r - 2; i >= l; --i) {
            if (hld && depth[csr[i + 1].to] == -1) swap(csr[i], csr[i + 1]);
        }
        int hld_sz = 0;
        for (int i = l; i < r; ++i) {
            auto e = csr[i];
            if (depth[e.to] != -1) continue;
            depth_weighted[e.to] = depth_weighted[v] + e.cost;
            VtoE[e.to] = e.id;
            dfs_sz(e.to, v, hld);
            sz[v] += sz[e.to];
            if (hld && chmax(hld_sz, sz[e.to]) && l < i) { swap(csr[l], csr[i]); }
        }
    }

    void dfs_hld(int v, int &times) {
        LID[v] = times++;
        RID[v] += LID[v];
        V[LID[v]] = v;
        bool heavy = true;
        for (auto &&e: G[v]) {
            if (depth[e.to] <= depth[v]) continue;
            head[e.to] = (heavy ? head[v] : e.to);
            heavy = false;
            dfs_hld(e.to, times);
        }
    }

    vector<int> heavy_path_at(int v) {
        vector<int> P = {v};
        while (1) {
            int a = P.back();
            for (auto &&e: G[a]) {
                if (e.to != parent[a] && head[e.to] == v) {
                    P.emplace_back(e.to);
                    break;
                }
            }
            if (P.back() == a) break;
        }
        return P;
    }

    int heavy_child(int v) {
        int k = LID[v] + 1;
        if (k == N) return -1;
        int w = V[k];
        return (parent[w] == v ? w : -1);
    }

    int e_to_v(int eid) {
        auto e = G.edges[eid];
        return (parent[e.frm] == e.to ? e.frm : e.to);
    }

    int v_to_e(int v) { return VtoE[v]; }
    int get_eid(int u, int v) {
        if (parent[u] != v) swap(u, v);
        assert(parent[u] == v);
        return VtoE[u];
    }
    int ELID(int v) { return 2 * LID[v] - depth[v]; }
    int ERID(int v) { return 2 * RID[v] - depth[v] - 1; }

    /* k: 0-indexed */
    int la(int v, int k) {
        assert(k <= depth[v]);
        while (1) {
            int u = head[v];
            if (LID[v] - k >= LID[u]) return V[LID[v] - k];
            k -= LID[v] - LID[u] + 1;
            v = parent[u];
        }
    }

    int lca(int u, int v) {
        for (;; v = parent[head[v]]) {
            if (LID[u] > LID[v]) swap(u, v);
            if (head[u] == head[v]) return u;
        }
    }

    int meet(int a, int b, int c) { return lca(a, b) ^ lca(a, c) ^ lca(b, c); }

    int lca_root(int u, int v, int root) {
        return lca(u, v) ^ lca(u, root) ^ lca(v, root);
    }

    int subtree_size(int v, int root = -1) {
        if (root == -1) return RID[v] - LID[v];
        if (v == root) return N;
        int x = jump(v, root, 1);
        if (in_subtree(v, x)) return RID[v] - LID[v];
        return N - RID[x] + LID[x];
    }

    int dist(int a, int b) {
        int c = lca(a, b);
        return depth[a] + depth[b] - 2 * depth[c];
    }

    WT dist_weighted(int a, int b) {
        int c = lca(a, b);
        return depth_weighted[a] + depth_weighted[b] - WT(2) * depth_weighted[c];
    }

    // a is in b
    bool in_subtree(int a, int b) { return LID[b] <= LID[a] && LID[a] < RID[b]; }

    int jump(int a, int b, long long k) {
        if (k == 1) {
            if (a == b) return -1;
            return (in_subtree(b, a) ? la(b, depth[b] - depth[a] - 1) : parent[a]);
        }
        int c = lca(a, b);
        int d_ac = depth[a] - depth[c];
        int d_bc = depth[b] - depth[c];
        if (k > d_ac + d_bc) return -1;
        if (k <= d_ac) return la(a, k);
        return la(b, d_ac + d_bc - k);
    }

    vector<int> collect_child(int v) {
        vector<int> res;
        for (auto &&e: G[v]) if (e.to != parent[v]) res.emplace_back(e.to);
        return res;
    }

    vector<int> collect_light(int v) {
        vector<int> res;
        bool skip = true;
        for (auto &&e: G[v])
            if (e.to != parent[v]) {
                if (!skip) res.emplace_back(e.to);
                skip = false;
            }
        return res;
    }

    vector<pair<int, int>> get_path_decomposition(int u, int v, bool edge) {
        vector<pair<int, int>> up, down;
        while (1) {
            if (head[u] == head[v]) break;
            if (LID[u] < LID[v]) {
                down.emplace_back(LID[head[v]], LID[v]);
                v = parent[head[v]];
            } else {
                up.emplace_back(LID[u], LID[head[u]]);
                u = parent[head[u]];
            }
        }
        if (LID[u] < LID[v]) down.emplace_back(LID[u] + edge, LID[v]);
        else if (LID[v] + edge <= LID[u]) up.emplace_back(LID[u], LID[v] + edge);
        reverse(down.begin(), down.end());
        up.insert(up.end(), down.begin(), down.end());
        return up;
    }

    vector<int> restore_path(int u, int v) {
        vector<int> P;
        for (auto &&[a, b]: get_path_decomposition(u, v, 0)) {
            if (a <= b) for (int i = a; i <= b; i++) P.emplace_back(V[i]);
            else for (int i = a; i >= b; i--) P.emplace_back(V[i]);
        }
        return P;
    }

    // path intersection of [a, b] x [c, d]
    // {-1, -1} if there wasn't any intersection
    // https://codeforces.com/problemset/problem/500/G
    pair<int, int> path_intersection(int a, int b, int c, int d) {
        int ab = lca(a, b), ac = lca(a, c), ad = lca(a, d);
        int bc = lca(b, c), bd = lca(b, d), cd = lca(c, d);
        int x = ab ^ ac ^ bc, y = ab ^ ad ^ bd; // meet(a,b,c), meet(a,b,d)
        if (x != y) return {x, y};
        int z = ac ^ ad ^ cd;
        if (x != z) x = -1;
        return {x, x};
    }
};
} // namespace mitsuha

namespace mitsuha{
template <typename TREE, typename Data>
struct Rerooting_dp {
    static_assert(!TREE::Graph_type::is_directed);
    TREE& tree;
    vector<Data> dp_1; // For edge pv, subtree v
    vector<Data> dp_2; // For edge pv, subtree p
    vector<Data> dp;   // full tree

    template <typename RAKE, typename APPLY_VERTEX, 
                                typename APPLY_EDGE>
    Rerooting_dp(TREE& tree, RAKE rake, APPLY_VERTEX apply_vertex, 
                            APPLY_EDGE apply_edge, const Data unit)
            : tree(tree) {
        build(rake, apply_vertex, apply_edge, unit);
    }
    
    Data operator[](int v) { return dp[v]; }

    // Subtree v when root is the root
    Data get(int v, int root) {
        if (root == v) return dp[v];
        if (!tree.in_subtree(root, v)) { return dp_1[v]; }
        int w = tree.jump(v, root, 1);
        return dp_2[w];
    }

    template <typename RAKE, typename APPLY_VERTEX, 
                                typename APPLY_EDGE>
    void build(RAKE rake, APPLY_VERTEX apply_vertex, 
                    APPLY_EDGE apply_edge, const Data unit) {
        int N = tree.N;
        // dp1: subtree
        dp_1.assign(N, unit);
        Frr(i, N) {
            int v = tree.V[i];
            for (auto&& e: tree.G[v]) {
                if (e.to == tree.parent[v]) continue;
                dp_1[v] = rake(dp_1[v], apply_edge(dp_1[e.to], e));
            }
            dp_1[v] = apply_vertex(dp_1[v], v);
        }

        // dp2[v]: subtree of p, rooted at v
        dp_2.assign(N, unit);
        // dp[v]: fulltree, rooted at v
        dp.assign(N, unit);
        For(i, N) {
            int p = tree.V[i];
            vector<int> ch;
            vector<Data> ch_data;
            Data x = unit;
            for (auto&& e: tree.G[p]) {
                if (e.to == tree.parent[p]) {
                    x = apply_edge(dp_2[p], e);
                } else {
                    ch.emplace_back(e.to);
                    ch_data.emplace_back(apply_edge(dp_1[e.to], e));
                }
            }
            int n = len(ch);
            if (!n) {
                dp[p] = apply_vertex(x, p);
                continue;
            }
            vector<Data> prod_left(n, x);
            For(i, n - 1) prod_left[i + 1] = rake(prod_left[i], ch_data[i]);
            Data prod_right = unit;
            Frr(i, n) {
                dp_2[ch[i]] = apply_vertex(rake(prod_left[i], prod_right), p);
                prod_right = rake(prod_right, ch_data[i]);
            }
            dp[p] = apply_vertex(rake(x, prod_right), p);
        }
    }
};
} // namespace mitsuha

/*
auto rake = [&](Data x, Data y) { return Data{}; };
auto apply_vertex = [&](Data x, int v) { return x; };
auto apply_edge = [&](Data x, auto& e) { return x; };

For each vertex u in reversed dfs order, set dp[u] = unit
For each child v of u with edge id, set dp[u] = rake(dp[u], apply_edge(f[v], id))
Finally, set dp[u] = apply_vertex(u, dp[u])

When dealing with size, Dont intitalize one in ideal elem,
Inc in apply_vertex because apply_vertex will be executed even if it has no childs

Note: edge id is directed opposite to dp direction
Note: Ideal should be purly Ideal, because it can multiply any times.
*/

int main(){
    
    Int(n);
    Graph<int> G(n);
    G.read_tree();
    
    Tree<decltype(G)> T(G);

    using Data = int;
    auto rake = [&](Data x, Data y) { return x + y; };
    auto apply_vertex = [&](Data x, int v) {
        if (G.deg(v) == 3) return x;
        if (G.deg(v) == 2) return 1;
        return 0;
    };
    auto apply_edge = [&](Data x, auto& e) { return x; };

    Rerooting_dp<decltype(T), Data> Rdp(T, rake, apply_vertex, apply_edge, 0);
    long long ret = 0;

    For(x, n){
        if (G.deg(x) == 2){
            for (auto &ed: G[x]){
                ret += Rdp.get(ed.to, x);
                ret -= G.deg(ed.to) == 2;
            }
        }
    }
    assert(~ret & 1);
    print(ret >> 1);
    
    return 0;
}

Submission Info

Compile Error

Main.cpp: In instantiation of ‘main()::<lambda(Data, auto:54&)> [with auto:54 = const mitsuha::Edge<int>; Data = int]’:
Main.cpp:820:51:   required from ‘void mitsuha::Rerooting_dp<TREE, Data>::build(RAKE, APPLY_VERTEX, APPLY_EDGE, Data) [with RAKE = main()::<lambda(Data, Data)>; APPLY_VERTEX = main()::<lambda(Data, int)>; APPLY_EDGE = main()::<lambda(Data, auto:54&)>; TREE = mitsuha::Tree<mitsuha::Graph<int> >; Data = int]’
Main.cpp:796:14:   required from ‘mitsuha::Rerooting_dp<TREE, Data>::Rerooting_dp(TREE&, RAKE, APPLY_VERTEX, APPLY_EDGE, Data) [with RAKE = main()::<lambda(Data, Data)>; APPLY_VERTEX = main()::<lambda(Data, int)>; APPLY_EDGE = main()::<lambda(Data, auto:54&)>; TREE = mitsuha::Tree<mitsuha::Graph<int> >; Data = int]’
Main.cpp:893:77:   required from here
Main.cpp:891:41: warning: unused parameter ‘e’ [-Wunused-parameter]
  891 |     auto apply_edge = [&](Data x, auto& e) { return x; };
      |                                   ~~~~~~^

Judge Result