#878380 (C++17) No.1637 Easy Tree Query

提出ソース

結果

問題	No.1637 Easy Tree Query
ユーザー	rokahikou1
提出日時	2023-06-06 00:05:11
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	58 ms / 2,000 ms
コード長	11,581 bytes
コンパイル時間	1,907 ms
コンパイル使用メモリ	210,224 KB
実行使用メモリ	14,096 KB
最終ジャッジ日時	2024-06-09 05:21:45
合計ジャッジ時間	5,459 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	52 ms 11,796 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	24 ms 7,432 KB
testcase_05	AC	36 ms 6,940 KB
testcase_06	AC	25 ms 6,940 KB
testcase_07	AC	11 ms 6,940 KB
testcase_08	AC	18 ms 6,940 KB
testcase_09	AC	40 ms 9,380 KB
testcase_10	AC	18 ms 6,940 KB
testcase_11	AC	50 ms 10,080 KB
testcase_12	AC	44 ms 8,504 KB
testcase_13	AC	11 ms 6,940 KB
testcase_14	AC	34 ms 9,424 KB
testcase_15	AC	49 ms 10,292 KB
testcase_16	AC	46 ms 11,032 KB
testcase_17	AC	15 ms 6,940 KB
testcase_18	AC	33 ms 6,944 KB
testcase_19	AC	35 ms 6,940 KB
testcase_20	AC	46 ms 8,204 KB
testcase_21	AC	28 ms 7,464 KB
testcase_22	AC	56 ms 11,196 KB
testcase_23	AC	16 ms 6,940 KB
testcase_24	AC	25 ms 7,468 KB
testcase_25	AC	35 ms 6,944 KB
testcase_26	AC	47 ms 9,096 KB
testcase_27	AC	58 ms 10,844 KB
testcase_28	AC	27 ms 6,940 KB
testcase_29	AC	37 ms 8,132 KB
testcase_30	AC	24 ms 7,984 KB
testcase_31	AC	20 ms 6,940 KB
testcase_32	AC	22 ms 6,944 KB
testcase_33	AC	31 ms 6,940 KB
testcase_34	AC	33 ms 14,096 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma region Macros
#include <bits/stdc++.h>
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int(i) = (n)-1; (i) >= 0; (i)--)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define ROF(i, m, n) for(int(i) = (n)-1; (i) >= (m); (i)--)
#define ALL(v) (v).begin(), (v).end()
#define LLA(v) (v).rbegin(), (v).rend()
#define SZ(v) (int)(v).size()
#define INT(...)     \
    int __VA_ARGS__; \
    read(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    read(__VA_ARGS__)
#define DOUBLE(...)     \
    double __VA_ARGS__; \
    read(__VA_ARGS__)
#define CHAR(...)     \
    char __VA_ARGS__; \
    read(__VA_ARGS__)
#define STRING(...)     \
    string __VA_ARGS__; \
    read(__VA_ARGS__)
#define VEC(type, name, size) \
    vector<type> name(size);  \
    read(name)
#define VEC2(type, name, height, width)                     \
    vector<vector<type>> name(height, vector<type>(width)); \
    read(name)
#define DVEC(type, name1, name2, size)     \
    vector<type> name1(size), name2(size); \
    read(name1, name2)
#define TVEC(type, name1, name2, name3, size)           \
    vector<type> name1(size), name2(size), name3(size); \
    read(name1, name2, name3)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;
const char newl = '\n';
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
template <class T> inline bool between(T x, T l, T r) {
    return l <= x && x < r;
}
template <class T> inline vector<T> make_vec(size_t a, T val) {
    return vector<T>(a, val);
}
template <class... Ts> inline auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec(ts...))>(a, make_vec(ts...));
}
void read() {}
template <class T> inline void read(T &a) { cin >> a; }
template <class T, class S> inline void read(pair<T, S> &p) {
    read(p.first), read(p.second);
}
template <class T> inline void read(vector<T> &v) {
    for(auto &&a : v)
        read(a);
}
template <class T, class U> inline void read(vector<T> &a, vector<U> &b) {
    for(int i = 0; i < a.size(); i++) {
        read(a[i]);
        read(b[i]);
    }
}
template <class T, class U, class V>
inline void read(vector<T> &a, vector<U> &b, vector<V> &c) {
    for(int i = 0; i < a.size(); i++) {
        read(a[i]);
        read(b[i]);
        read(c[i]);
    }
}
template <class Head, class... Tail>
inline void read(Head &head, Tail &...tail) {
    read(head), read(tail...);
}
template <class T> void _write(const T &a) { cout << a; }
template <class T, class U> void _write(const std::pair<T, U> &a) { cout << a.first << ' ' << a.second; }
template <class T> void write(const T &a) {
    _write(a);
    cout << newl;
}
template <class T> void write(const vector<T> &a) {
    for(int i = 0; i < a.size(); i++) {
        _write(a[i]);
        cout << (i + 1 == a.size() ? newl : ' ');
    }
}
template <class Head, class... Tail>
void write(const Head &head, const Tail &...tail) {
    _write(head);
    cout << ' ';
    write(tail...);
}
template <class T> void writel(const T &a) { cout << a << '\n'; }
template <class T> void writel(const vector<T> &a) {
    for(int i = 0; i < a.size(); i++) {
        _write(a[i]);
        cout << newl;
    }
}
template <class Head, class... Tail>
void writel(const Head &head, const Tail &...tail) {
    _write(head);
    cout << newl;
    write(tail...);
}
template <class T> void _debug(const T &a) { cerr << a; }
template <class T, class U> void _debug(const std::pair<T, U> &a) { cerr << a.first << ' ' << a.second; }
template <class T> void debug(const T &a) {
    _debug(a);
    cerr << newl;
}
template <class T> void debug(const vector<T> &a) {
    for(int i = 0; i < a.size(); i++) {
        _debug(a[i]);
        cerr << (i + 1 == a.size() ? newl : ' ');
    }
}
template <class Head, class... Tail>
void debug(const Head &head, const Tail &...tail) {
    _debug(head);
    cerr << ' ';
    debug(tail...);
}
template <class T> void debugl(const T &a) { cerr << a << '\n'; }
template <class T> void debugl(const vector<T> &a) {
    for(int i = 0; i < a.size(); i++) {
        _debug(a[i]);
        cerr << newl;
    }
}
template <class Head, class... Tail>
void debugl(const Head &head, const Tail &...tail) {
    _debug(head);
    cerr << newl;
    debug(tail...);
}
template <class T> auto sum(const vector<T> &a) {
    return accumulate(ALL(a), T(0));
}
template <class T> auto min(const vector<T> &a) { return *min_element(ALL(a)); }
template <class T> auto max(const vector<T> &a) { return *max_element(ALL(a)); }
template <class T, class U> void msort(vector<T> &a, vector<U> &b) {
    assert(a.size() == b.size());
    vector<pair<T, U>> ab(a.size());
    for(int i = 0; i < a.size(); i++)
        ab[i] = {a[i], b[i]};
    sort(ALL(ab));
    for(int i = 0; i < a.size(); i++) {
        a[i] = ab[i].first;
        b[i] = ab[i].second;
    }
}
template <class T, class U, class V>
void msort(vector<T> &a, vector<U> &b, vector<V> &c) {
    assert(a.size() == b.size() && b.size() == c.size());
    vector<tuple<T, U, V>> abc(a.size());
    for(int i = 0; i < a.size(); i++)
        abc[i] = {a[i], b[i], c[i]};
    sort(ALL(abc));
    for(int i = 0; i < a.size(); i++) {
        a[i] = get<0>(abc[i]);
        b[i] = get<1>(abc[i]);
        c[i] = get<2>(abc[i]);
    }
}
template <class T, class U> inline bool chmax(T &a, U b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T, class U> inline bool chmin(T &a, U b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
int digit(ll a) {
    ll ret = 0;
    while(a && ++ret)
        a /= 10;
    return ret;
}
int digit_sum(ll a) {
    ll ret = 0;
    while(a) {
        ret += a % 10;
        a /= 10;
    }
    return ret;
}
ll llpow(ll a, ll n) {
    ll ret = 1;
    rep(i, n) ret *= a;
    return ret;
}
inline int bsf(int v) { return __builtin_ctz(v); } // 最下位の1が下から何番目か
inline int bsf(ll v) { return __builtin_ctzll(v); }
inline int bsr(int v) {
    return 31 - __builtin_clz(v);
} // 最上位の1が下から何番目か
inline int bsr(ll v) { return 63 - __builtin_clzll(v); }
inline int lsb(int v) { return v & -v; }      // 最下位の1だけ残す
inline ll lsb(ll v) { return v & -v; }
inline int msb(int v) { return 1 << bsr(v); } // 最上位の1だけ残す
inline ll msb(ll v) { return 1LL << bsr(v); }
struct IO {
    IO() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(10);
    }
} io;
#pragma endregion

template <typename T = int> class Graph {
  public:
    class Edge {
      public:
        int from, to;
        T cost;
        Edge() = default;
        Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
        bool operator<(const Edge &rhs) const {
            return cost < rhs.cost;
        }
    };
    vector<vector<Edge>> g;
    vector<Edge> edges;
    int n;
    const T INF = numeric_limits<T>::max();
    Graph() = default;
    Graph(int n) : n(n), g(n) {}
    vector<Edge> &operator[](int k) { return g[k]; }
    const vector<Edge> &operator[](int k) const { return g[k]; }

    int size() const { return g.size(); }
    void resize(size_t sz) { g.resize(sz, vector<Edge>()); }

    void add_edge(int u, int v) {
        g[u].push_back(Edge(u, v, 1));
        edges.push_back(Edge(u, v, 1));
    }
    void add_edge(int u, int v, T c) {
        g[u].push_back(Edge(u, v, c));
        edges.push_back(Edge(u, v, c));
    }
    void unite(int u, int v) {
        g[u].push_back(Edge(u, v, 1));
        g[v].push_back(Edge(v, u, 1));
        edges.push_back(Edge(u, v, 1));
    }
    void unite(int u, int v, T c) {
        g[u].push_back(Edge(u, v, c));
        g[v].push_back(Edge(v, u, c));
        edges.push_back(Edge(u, v, c));
    }

    vector<T> dijkstra(int s) {
        priority_queue<pair<T, int>, vector<pair<T, int>>,
                       greater<pair<T, int>>>
            que;
        vector<T> dist(n, INF);
        dist[s] = 0;
        que.push(make_pair(0, s));
        while(!que.empty()) {
            pair<T, int> p = que.top();
            que.pop();
            int v = p.second;
            if(dist[v] < p.first)
                continue;
            for(auto e : g[v]) {
                if(dist[e.to] > dist[v] + e.cost) {
                    dist[e.to] = dist[v] + e.cost;
                    que.push(make_pair(dist[e.to], e.to));
                }
            }
        }
        for(int i = 0; i < n; i++)
            if(dist[i] == INF)
                dist[i] = -1;
        return dist;
    }

    pair<bool, vector<T>> bellman_ford(int s) {
        int n = g.size();
        vector<ll> dist(n, INF);
        bool negative_cycle = false;
        dist[s] = 0;
        for(int i = 0; i < n; i++) {
            for(int v = 0; v < n; v++) {
                for(auto e : g[v]) {
                    if(dist[v] != INF && dist[e.to] > dist[v] + e.cost) {
                        dist[e.to] = dist[v] + e.cost;
                        if(i == n - 1) {
                            dist[e.to] = -INF;
                            negative_cycle = true;
                        }
                    }
                }
            }
        }
        return {negative_cycle, dist};
    }

    // 0 or 1
    vector<int> bipartite_split() {
        vector<int> ret(n, -1);
        auto dfs = [&](auto &&dfs, int v, int p, bool pcolor) -> bool {
            ret[v] = !pcolor;
            for(auto e : g[v]) {
                if(v == p) continue;
                if(ret[v] == ret[e.to]) return false;
                if(ret[e.to] == -1 && !dfs(dfs, e.to, v, ret[v])) return false;
            }
            return true;
        };
        for(int i = 0; i < n; i++) {
            if(ret[i] == -1 && !dfs(dfs, i, -1, 0)) return vector<int>();
        }
        return ret;
    }

    template <class UnionFind> pair<ll, vector<Edge>> kruskal() {
        T sum = 0;
        sort(edges.begin(), edges.end());
        vector<Edge> ret;
        UnionFind uf(n);
        for(auto e : edges) {
            if(!uf.same(e.from, e.to)) {
                uf.unite(e.from, e.to);
                ret.push_back(e);
                sum += e.cost;
            }
        }
        return make_pair(sum, ret);
    }

    vector<int> topological_sort() {
        vector<int> ret;
        stack<int> st;
        vector<int> in(n);
        for(int i = 0; i < n; i++) {
            for(auto e : g[i]) {
                in[e.to] += 1;
            }
        }
        for(int i = 0; i < in.size(); i++)
            if(in[i] == 0)
                st.push(i);
        while(!st.empty()) {
            int v = st.top();
            st.pop();
            ret.push_back(v);
            for(auto e : g[v]) {
                in[e.to]--;
                if(in[e.to] == 0)
                    st.push(e.to);
            }
        }
        return ret;
    }
};

void solve() {
    INT(n, Q);
    Graph g(n);
    rep(i, n - 1) {
        INT(a, b);
        a--, b--;
        g.unite(a, b);
    }
    vector<int> siz(n);
    auto f = [&](auto &&f, int v, int p) -> int {
        int s = 1;
        for(auto e : g[v]) {
            if(e.to == p) continue;
            s += f(f, e.to, v);
        }
        return siz[v] = s;
    };
    f(f, 0, -1);
    ll res = 0;
    rep(i, Q) {
        LL(p, x);
        p--;
        res += x * siz[p];
        write(res);
    }
}

int main() {
    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
}

yukicoder

結果

テストケース

ソースコード