#1027843 (C++23) No.399 動的な領主

提出ソース
結果

問題	No.399 動的な領主
ユーザー	ooaiu
提出日時	2024-11-21 13:12:59
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	100 ms / 2,000 ms
コード長	13,978 bytes
コンパイル時間	3,796 ms
コンパイル使用メモリ	271,692 KB
実行使用メモリ	22,268 KB
最終ジャッジ日時	2024-11-21 13:13:06
合計ジャッジ時間	5,906 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	6 ms 5,248 KB
testcase_06	AC	100 ms 14,468 KB
testcase_07	AC	85 ms 14,600 KB
testcase_08	AC	73 ms 14,476 KB
testcase_09	AC	75 ms 14,604 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	5 ms 5,248 KB
testcase_12	AC	56 ms 15,136 KB
testcase_13	AC	56 ms 14,880 KB
testcase_14	AC	36 ms 22,264 KB
testcase_15	AC	37 ms 22,268 KB
testcase_16	AC	33 ms 18,296 KB
testcase_17	AC	74 ms 14,348 KB
testcase_18	AC	80 ms 14,476 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifndef LOCAL
#include <bits/stdc++.h>

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128_t;
using u128 = __uint128_t;

namespace fastio {
static constexpr int BUF_SIZE = 1 << 20;

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

static struct FastOutput {
   private:
    static constexpr int TMP_SIZE = 1 << 10;
    char tmp[TMP_SIZE];
    char buf[BUF_SIZE];
    size_t buf_pos = 0;

    template <class T>
    inline char* wt_integer(T x) {
        char* p = tmp + TMP_SIZE - 1;
        if (x == 0) {
            *--p = '0';
        } else {
            bool is_negative = false;
            if (x < 0) {
                is_negative = true;
                x = -x;
            }
            while (x >= 10000) {
                memcpy(p -= 4, pre.num[x % 10000], 4);
                x /= 10000;
            }
            if (x >= 1000) {
                memcpy(p -= 4, pre.num[x], 4);
            } else if (x >= 100) {
                memcpy(p -= 3, pre.num[x] + 1, 3);
            } else if (x >= 10) {
                memcpy(p -= 2, pre.num[x] + 2, 2);
            } else {
                *--p = pre.num[x][3];
            }
            if (is_negative) *--p = '-';
        }
        return p;
    }

    template <class T, size_t N = 0>
    inline 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<T, N + 1>(t);
        }
    }

   public:
    inline void wt(char c) {
        buf[buf_pos++] = c;
        if (buf_pos == BUF_SIZE) flush();
    }

    inline void wt(const char* s) {
        for (; *s != '\0'; s++) {
            wt(*s);
        }
    }

    inline void wt(const std::string& s) {
        for (char c : s) wt(c);
    }

    template <class Tp>
    inline std::enable_if_t<std::is_floating_point_v<Tp>>
    wt(const Tp& x) {
        std::ostringstream oss;
        oss << std::fixed << std::setprecision(16) << x;
        wt(oss.str());
    }

    template <class Tp>
    inline std::enable_if_t<std::is_integral_v<Tp>>
    wt(const Tp& x) { wt(wt_integer(x)); }

    inline void wt(const __int128_t& x) { wt(wt_integer(x)); }
    inline void wt(const __uint128_t& x) { wt(wt_integer(x)); }

    template <class T, class U>
    inline void wt(const std::pair<T, U>& p) {
        wt(p.first);
        wt(' ');
        wt(p.second);
    }

    template <class... Args>
    inline void wt(const std::tuple<Args...>& t) {
        wt_tuple(t);
    }

    template <class T, size_t N = 0>
    inline void wt(const std::array<T, N>& a) {
        for (size_t i = 0; i < N; i++) {
            if (i) wt(' ');
            wt(a[i]);
        }
    }
    template <class T>
    inline void wt(const std::vector<T>& x) {
        for (size_t i = 0; i < x.size(); i++) {
            if (i) wt(' ');
            wt(x[i]);
        }
    }

    inline void flush() {
        fwrite(buf, 1, buf_pos, stdout);
        buf_pos = 0;
    }
    ~FastOutput() { flush(); }
} fastout;

static struct FastInput {
   private:
    char buf[BUF_SIZE];
    size_t buf_pos = 0;
    size_t size = 0;
    char cur = 0;
    inline char rd_char() {
        if (buf_pos >= size) {
            size = fread(buf, 1, BUF_SIZE, stdin);
            buf_pos = 0;
            buf[0] = (size == 0 ? -1 : buf[0]);
        }
        return cur = buf[buf_pos++];
    }

    template <class Tp>
    inline void rd_integer(Tp& x) {
        x = Tp{};
        if (skip_blanks()) {
            int sign = +1;
            if (cur == '-') {
                sign = -1;
                rd_char();
            }
            do {
                x += x + (x << 3) + (cur & 15);
            } while (!is_blank(rd_char()));
            x *= sign;
        }
    }

    inline bool is_blank(char c) { return c <= ' '; }

    inline bool skip_blanks() {
        while (is_blank(cur) && cur != -1) {
            rd_char();
        }
        return cur != -1;
    }

    template <class T, size_t N = 0>
    void rd_tuple(T& t) {
        if constexpr (N < std::tuple_size<T>::value) {
            auto& x = std::get<N>(t);
            rd(x);
            rd_tuple<T, N + 1>(t);
        }
    }

   public:
    inline void rd(char& c) {
        skip_blanks();
        c = cur;
    }

    inline void rd(std::string& s) {
        if (skip_blanks()) {
            s.clear();
            do {
                s += cur;
            } while (!is_blank(rd_char()));
        }
    }

    template <class T>
    inline auto rd(T& x) -> std::void_t<std::enable_if_t<std::is_integral<T>::value>> { rd_integer(x); }
    inline auto rd(__int128_t& x) { rd_integer(x); }
    inline auto rd(__uint128_t& x) { rd_integer(x); }

    inline void rd(double& x) {
        std::string s;
        rd(s);
        x = std::stod(s);
    }

    inline void rd(long double& x) {
        std::string s;
        rd(s);
        x = std::stold(s);
    }

    template <class T, class U>
    void rd(std::pair<T, U>& p) {
        rd(p.first);
        rd(p.second);
    }

    template <class... Args>
    void rd(std::tuple<Args...>& t) {
        rd_tuple(t);
    }

    template <class T, size_t N>
    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);
    }
} fastin;

inline void flush() { fastout.flush(); }
void IN() {}
template <class Head, class... Tails>
void IN(Head& head, Tails&... tails) {
    fastin.rd(head);
    IN(tails...);
}
template <class Last>
void print(const Last& last) { fastout.wt(last); }
template <class Head, class... Tails>
void print(const Head& head, const Tails&... tails) {
    fastout.wt(head);
    fastout.wt(' ');
    print(tails...);
}
template <class... Args>
void println(const Args&... args) {
    print(args...);
    fastout.wt('\n');
}
}  // namespace fastio
using fastio::flush;
using fastio::IN;
using fastio::print;
using fastio::println;

#define INT(...)     \
    int __VA_ARGS__; \
    IN(__VA_ARGS__)
#define LL(...)            \
    long long __VA_ARGS__; \
    IN(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    IN(__VA_ARGS__)
#define CHAR(...)     \
    char __VA_ARGS__; \
    IN(__VA_ARGS__)
#define DBL(...)        \
    double __VA_ARGS__; \
    IN(__VA_ARGS__)

#define VEC(type, name, size) \
    vector<type> name(size);  \
    IN(name)

#define VV(type, name, h, w)                       \
    vector<vector<type>> name(h, vector<type>(w)); \
    IN(name)

#define debug(...) (void(0))
#else
#include "algo/debug.h"
#endif

template <class T>
struct Edge {
    int from;
    int to;
    T cost;
    friend bool operator<(const Edge<T>& lhs, const Edge<T>& rhs) {
        return lhs.cost < rhs.cost;
    }
    friend bool operator>(const Edge<T>& lhs, const Edge<T>& rhs) {
        return lhs.cost > rhs.cost;
    }
};

template <class T>
struct Graph : public Edge<T> {
    int N, M;
    std::vector<std::vector<int>> G;
    std::vector<Edge<T>> edges;

    Graph() : N(0), M(0) {}
    explicit Graph(int n) : N(n), M(0), G(n) {}

    int add(int from, int to, T cost = 1, bool is_dir = false) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        edges.push_back({from, to, cost});
        G[from].push_back(M);
        if (!is_dir) G[to].push_back(M);
        return M++;
    }

    const std::vector<int>& operator[](int p) const { return G[p]; }
    std::vector<int>& operator[](int p) { return G[p]; }
};

template <class T>
struct HeavyLightDecomposition {
    std::vector<int> sz, head, in, out, par, dep, vid;

   private:
    int N, k;
    const Graph<T>& G;
    int dfs_sz(int v, int p = -1) {
        sz[v] = 1;
        for (int id : G[v]) {
            const auto& e = G.edges[id];
            int to = v ^ e.from ^ e.to;
            if (to == p) continue;
            dep[to] = dep[v] + 1;
            sz[v] += dfs_sz(to, v);
        }
        return sz[v];
    }
    void dfs_hld(int v, int p = -1) {
        in[v] = k++;
        vid[in[v]] = v;
        par[v] = p;
        int best = -1, bnode = -1;
        for (const int id : G[v]) {
            const auto& e = G.edges[id];
            int to = v ^ e.from ^ e.to;
            if (to == p) continue;
            if (sz[to] > best) {
                best = sz[to];
                bnode = to;
            }
        }
        if (bnode != -1) {
            head[bnode] = head[v];
            dfs_hld(bnode, v);
        }
        for (const int id : G[v]) {
            const auto& e = G.edges[id];
            int to = v ^ e.from ^ e.to;
            if (to == p || to == bnode) continue;
            head[to] = to;
            dfs_hld(to, v);
        }
        out[v] = k;
    }

   public:
    HeavyLightDecomposition() = default;
    HeavyLightDecomposition(const Graph<T>& g, int root = 0)
        : HeavyLightDecomposition(g, std::vector<int>{root}) {}
    HeavyLightDecomposition(const Graph<T>& g, const std::vector<int>& roots) : G(g) {
        N = G.N;
        sz.assign(N, -1);
        dep.resize(N);
        for (int r : roots) dfs_sz(r);
        for (int i = 0; i < N; i++)
            if (sz[i] == -1) dfs_sz(i);
        k = 0;
        head.assign(N, -1);
        in.resize(N);
        out.resize(N);
        par.assign(N, -1);
        vid.resize(N);
        for (int r : roots) {
            head[r] = r;
            dfs_hld(r);
        }
        for (int i = 0; i < N; i++) {
            if (head[i] == -1) {
                head[i] = i;
                dfs_hld(i);
            }
        }
    }
    int get(int p) const { return in[p]; }
    int depth(int p) const { return dep[p]; }
    int operator[](int p) const { return get(p); }
    int size(int p) const { return sz[p]; }
    int kth_anc(int v, int k) {
        while (v >= 0) {
            int u = head[v];
            if (in[v] - k >= in[u]) return vid[in[v] - k];
            k -= in[v] - in[u] + 1;
            v = par[u];
        }
        return -1;
    }
    int jump(int u, int v, int d) {
        int l = lca(u, v);
        int d1 = dep[u] - dep[l];
        if (d <= d1) return kth_anc(u, d);
        int d2 = d1 + dep[v] - dep[l];
        if (d <= d2) return kth_anc(v, d2 - d);
        return -1;
    }
    std::pair<int, int> subtree(int p) const { return {in[p], out[p]}; }
    int lca(int u, int v) const {
        while (head[u] != head[v]) {
            if (in[u] > in[v]) std::swap(u, v);
            v = par[head[v]];
        }
        return in[u] > in[v] ? v : u;
    }
    std::vector<std::pair<int, int>> ascend(int u, int v) const {
        std::vector<std::pair<int, int>> res;
        while (head[u] != head[v]) {
            res.emplace_back(in[u], in[head[u]]);
            u = par[head[u]];
        }
        if (u != v) res.emplace_back(in[u], in[v] + 1);
        return res;
    }
    std::vector<std::pair<int, int>> descend(int u, int v) const {
        std::vector<std::pair<int, int>> res = ascend(v, u);
        for (auto&& [a, b] : res) std::swap(a, b);
        std::reverse(res.begin(), res.end());
        return res;
    }
    template <class F>
    void path_vertex(int u, int v, const F& f) const {
        path_vertex(u, v, f, f);
    }
    template <class F, class G>
    void path_vertex(int u, int v, const F& f, const G& g) const {
        int l = lca(u, v);
        const auto func = [&](int a, int b) -> void {
            if (a <= b)
                f(a, b + 1);
            else
                g(b, a + 1);
        };
        for (const auto& [a, b] : ascend(u, l)) func(a, b);
        func(in[l], in[l]);
        for (const auto& [a, b] : descend(l, v)) func(a, b);
    }
    template <class F>
    void path_edge(int u, int v, const F& f) const {
        return path_edge(u, v, f, f);
    }
    template <class F, class G>
    void path_edge(int u, int v, const F& f, const G& g) const {
        int l = lca(u, v);
        const auto func = [&](int a, int b) -> void {
            if (a <= b)
                f(a, b + 1);
            else
                g(b, a + 1);
        };
        for (const auto& [a, b] : ascend(u, l)) func(a, b);
        for (const auto& [a, b] : descend(l, v)) func(a, b);
    }
};

namespace std {

template <class Fun>
class y_combinator_result {
    Fun fun_;

   public:
    template <class T>
    explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}

    template <class... Args>
    decltype(auto) operator()(Args&&... args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

}  // namespace std

void solve() {
    using namespace std;
    INT(N);
    Graph<int> G(N);
    for (int i = 1; i < N; i++) {
        INT(u, v);
        u--;
        v--;
        G.add(u, v);
    }
    vector<long long> res(N);
    HeavyLightDecomposition hld(G);
    INT(Q);
    while (Q--) {
        INT(a, b);
        a--;
        b--;
        int l = hld.lca(a, b);
        res[a]++;
        res[b]++;
        res[l]--;
        if (hld.par[l] != -1) res[hld.par[l]]--;
    }
    y_combinator([&](auto dfs, int v, int p = -1) -> void {
        for (const int id : G[v]) {
            const auto& e = G.edges[id];
            int to = v ^ e.from ^ e.to;
            if (to == p) continue;
            dfs(to, v);
            res[v] += res[to];
        }
    })(0);
    long long ans = 0;
    for (int i = 0; i < N; i++) ans += res[i] * (res[i] + 1) / 2;
    println(ans);
}

int main() {
    int T = 1;
    // std::cin >> T;
    while (T--) {
        solve();
    }
}
yukicoder

結果

テストケース

ソースコード
