test/yukicoder/1790.test.cpp

• View this file on GitHub
• Last update: 2026-04-02 20:43:27+09:00
• Problem: https://yukicoder.me/problems/no/1790

Depends on

• 重み付きグラフ (lib/graph/graph.hpp)
• lib/segtree/monoid.hpp
• lib/tree/euler_tour_tree.hpp

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1790
#include <cstdint>
#include <iostream>
#include <tuple>
#include <vector>
#include "graph/graph.hpp"
#include "tree/euler_tour_tree.hpp"

int main(void) {
    int n;
    std::cin >> n;
    std::vector<std::tuple<int, int, std::int64_t>> edge(n - 1);
    for (auto &[u, v, x] : edge) {
        std::cin >> u >> v >> x;
        --u, --v;
    }

    Graph<void> g(2 * n - 1);
    std::vector<std::int64_t> a(2 * n - 1);
    for (int i = 0; i < n - 1; ++i) {
        auto [u, v, x] = edge[i];
        g.add_edges(u, n + i);
        g.add_edges(v, n + i);
        a[n + i] = x;
    }
    std::vector<int> par(2 * n - 1, -1);
    auto dfs = [&](auto self, int x, int p) -> void {
        par[x] = p;
        for (auto e : g[x]) {
            if (e.to() == p) continue;
            self(self, e.to(), x);
        }
    };
    dfs(dfs, 0, -1);

    euler_tour_tree<Xor<std::int64_t>> et(a);
    for (int i = 0; i < n - 1; ++i) {
        auto [u, v, x] = edge[i];
        et.link(u, n + i);
        et.link(v, n + i);
    }

    int q;
    std::cin >> q;
    while (q--) {
        int t, x;
        std::cin >> t >> x;
        --x;
        if (t == 1) {
            if (et.same(x, 0)) et.cut(par[x], par[par[x]]);
        } else {
            if (!et.same(x, 0)) std::cout << 0 << '\n';
            else std::cout << et.get_subtree(x, par[x]) << '\n';
        }
    }

    return 0;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/graph.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	01_sample_01	AC	2 ms	4 MB
g++	01_sample_02	AC	2 ms	4 MB
g++	01_sample_03	AC	2 ms	4 MB
g++	02_maxcase_01	AC	754 ms	83 MB
g++	02_maxcase_02	AC	670 ms	83 MB
g++	02_maxcase_03	AC	669 ms	83 MB
g++	02_maxcase_04	AC	774 ms	83 MB
g++	02_maxcase_05	AC	752 ms	83 MB
g++	03_mincase_01	AC	68 ms	4 MB
g++	04_fcase_01	AC	730 ms	83 MB
g++	04_fcase_02	AC	672 ms	83 MB
g++	04_fcase_03	AC	681 ms	83 MB
g++	05_randcase_01	AC	551 ms	78 MB
g++	05_randcase_02	AC	471 ms	66 MB
g++	05_randcase_03	AC	140 ms	20 MB

Back to top page