結果
問題 | No.2439 Fragile Apple Tree |
ユーザー |
|
提出日時 | 2023-08-12 13:36:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,993 ms / 10,000 ms |
コード長 | 11,362 bytes |
コンパイル時間 | 2,424 ms |
コンパイル使用メモリ | 168,020 KB |
最終ジャッジ日時 | 2025-02-16 03:11:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#line 1 "a.cpp"#include <atcoder/lazysegtree>#line 2 "graph/template.hpp"#include <vector>namespace ebi {template <class T> struct Edge {int to;T cost;Edge(int _to, T _cost = 1) : to(_to), cost(_cost) {}};template <class T> struct Graph : std::vector<std::vector<Edge<T>>> {using std::vector<std::vector<Edge<T>>>::vector;void add_edge(int u, int v, T w, bool directed = false) {(*this)[u].emplace_back(v, w);if (directed) return;(*this)[v].emplace_back(u, w);}};struct graph : std::vector<std::vector<int>> {using std::vector<std::vector<int>>::vector;void add_edge(int u, int v, bool directed = false) {(*this)[u].emplace_back(v);if (directed) return;(*this)[v].emplace_back(u);}};} // namespace ebi#line 1 "template/template.hpp"#include <algorithm>#include <bitset>#include <cassert>#include <chrono>#include <climits>#include <cmath>#include <complex>#include <cstddef>#include <cstdint>#include <cstdlib>#include <cstring>#include <functional>#include <iomanip>#include <iostream>#include <limits>#include <map>#include <memory>#include <numeric>#include <optional>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <type_traits>#include <unordered_map>#include <unordered_set>#include <utility>#line 31 "template/template.hpp"#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)#define rrep(i, a, n) for (int i = ((int)(n)-1); i >= (int)(a); i--)#define Rep(i, a, n) for (i64 i = (i64)(a); i < (i64)(n); i++)#define RRep(i, a, n) for (i64 i = ((i64)(n)-i64(1)); i >= (i64)(a); i--)#define all(v) (v).begin(), (v).end()#define rall(v) (v).rbegin(), (v).rend()#line 2 "template/debug_template.hpp"#line 4 "template/debug_template.hpp"namespace ebi {#ifdef LOCAL#define debug(...) \std::cerr << "LINE: " << __LINE__ << " [" << #__VA_ARGS__ << "]:", \debug_out(__VA_ARGS__)#else#define debug(...)#endifvoid debug_out() {std::cerr << std::endl;}template <typename Head, typename... Tail> void debug_out(Head h, Tail... t) {std::cerr << " " << h;if (sizeof...(t) > 0) std::cerr << " :";debug_out(t...);}}#line 2 "template/int_alias.hpp"#line 4 "template/int_alias.hpp"namespace ebi {using std::size_t;using i8 = std::int8_t;using u8 = std::uint8_t;using i16 = std::int16_t;using u16 = std::uint16_t;using i32 = std::int32_t;using u32 = std::uint32_t;using i64 = std::int64_t;using u64 = std::uint64_t;using i128 = __int128_t;using u128 = __uint128_t;}#line 2 "template/io.hpp"#line 6 "template/io.hpp"namespace ebi {template <typename T1, typename T2>std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &pa) {return os << pa.first << " " << pa.second;}template <typename T1, typename T2>std::istream &operator>>(std::istream &os, std::pair<T1, T2> &pa) {return os >> pa.first >> pa.second;}template <typename T>std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");return os;}template <typename T>std::istream &operator>>(std::istream &os, std::vector<T> &vec) {for (T &e : vec) std::cin >> e;return os;}template <typename T>std::ostream &operator<<(std::ostream &os, const std::optional<T> &opt) {if (opt) {os << opt.value();} else {os << "invalid value";}return os;}void fast_io() {std::cout << std::fixed << std::setprecision(15);std::cin.tie(nullptr);std::ios::sync_with_stdio(false);}} // namespace ebi#line 2 "template/utility.hpp"#line 5 "template/utility.hpp"#line 7 "template/utility.hpp"namespace ebi {template <class T> inline bool chmin(T &a, T b) {if (a > b) {a = b;return true;}return false;}template <class T> inline bool chmax(T &a, T b) {if (a < b) {a = b;return true;}return false;}constexpr i64 LNF = std::numeric_limits<i64>::max() / 4;constexpr int INF = std::numeric_limits<int>::max() / 2;const std::vector<int> dy = {1, 0, -1, 0, 1, 1, -1, -1};const std::vector<int> dx = {0, 1, 0, -1, 1, -1, 1, -1};} // namespace ebi#line 2 "tree/heavy_light_decomposition.hpp"#line 6 "tree/heavy_light_decomposition.hpp"namespace ebi {struct heavy_light_decomposition {private:void dfs_sz(int v) {for (auto &nv : g[v]) {if (nv == par[v]) continue;par[nv] = v;depth[nv] = depth[v] + 1;dfs_sz(nv);sz[v] += sz[nv];if (sz[nv] > sz[g[v][0]] || g[v][0] == par[v])std::swap(nv, g[v][0]);}}void dfs_hld(int v) {static int t = 0;in[v] = t++;rev[in[v]] = v;for (auto nv : g[v]) {if (nv == par[v]) continue;nxt[nv] = (nv == g[v][0] ? nxt[v] : nv);dfs_hld(nv);}out[v] = t;}// [u, v) パスの取得 (v は u の祖先)std::vector<std::pair<int, int>> ascend(int u, int v) const {std::vector<std::pair<int, int>> res;while (nxt[u] != nxt[v]) {res.emplace_back(in[u], in[nxt[u]]);u = par[nxt[u]];}if (u != v) res.emplace_back(in[u], in[v] + 1);return res;}// (u, v] パスの取得 (u は v の祖先)std::vector<std::pair<int, int>> descend(int u, int v) const {if (u == v) return {};if (nxt[u] == nxt[v]) return {{in[u] + 1, in[v]}};auto res = descend(u, par[nxt[v]]);res.emplace_back(in[nxt[v]], in[v]);return res;}public:heavy_light_decomposition(const std::vector<std::vector<int>> &gh,int root = 0): n(gh.size()),g(gh),sz(n, 1),in(n),out(n),nxt(n),par(n, -1),depth(n, 0),rev(n) {dfs_sz(root);dfs_hld(root);}int idx(int u) const {return in[u];}int la(int v, int k) const {while (1) {int u = nxt[v];if (in[u] <= in[v] - k) return rev[in[v] - k];k -= in[v] - in[u] + 1;v = par[u];}}int lca(int u, int v) const {while (nxt[u] != nxt[v]) {if (in[u] < in[v]) std::swap(u, v);u = par[nxt[u]];}return depth[u] < depth[v] ? u : v;}int jump(int s, int t, int i) const {if (i == 0) return s;int l = lca(s, t);int d = depth[s] + depth[t] - depth[l] * 2;if (d < i) return -1;if (depth[s] - depth[l] >= i) return la(s, i);i = d - i;return la(t, i);}std::vector<int> path(int s, int t) const {int l = lca(s, t);std::vector<int> a, b;for (; s != l; s = par[s]) a.emplace_back(s);for (; t != l; t = par[t]) b.emplace_back(t);a.emplace_back(l);std::reverse(b.begin(), b.end());a.insert(a.end(), b.begin(), b.end());return a;}int distance(int u, int v) const {return depth[u] + depth[v] - 2 * depth[lca(u, v)];}int distance_from_root(int v) const {return depth[v];}bool at_path(int u, int v, int s) const {return distance(u, v) == distance(u, s) + distance(s, v);}template <class F>void path_noncommutative_query(int u, int v, bool vertex,const F &f) const {int l = lca(u, v);for (auto [a, b] : ascend(u, l)) f(a + 1, b);if (vertex) f(in[l], in[l] + 1);for (auto [a, b] : descend(l, v)) f(a, b + 1);}template <class F> void subtree_query(int u, bool vertex, const F &f) {f(in[u] + int(!vertex), out[u]);}private:int n;std::vector<std::vector<int>> g;std::vector<int> sz, in, out, nxt, par, depth, rev;};} // namespace ebi#line 6 "a.cpp"namespace ebi {i64 op(i64 a, i64 b) {return a < b ? a : b;}i64 e() {return LNF;}i64 mapping(i64 f, i64 x) {return f + x;}i64 composition(i64 f, i64 g) {return f + g;}i64 id() {return 0;}void main_() {int n, q;std::cin >> n >> q;std::vector<i64> d(n, LNF);Graph<i64> g(n);graph gh(n);rep(i, 0, n - 1) {int a, b;i64 c;std::cin >> a >> b >> c;a--;b--;assert(0 <= a && a < n && 0 <= b && b < n);g.add_edge(a, b, c);gh.add_edge(a, b);}std::vector<int> par(n, -1);auto dfs_par = [&](auto &&self, int v) -> void {for (auto [nv, w] : g[v]) {if (nv == par[v]) continue;par[nv] = v;d[nv] = w;self(self, nv);}};dfs_par(dfs_par, 0);int ans = n;std::vector<int> mark(n, -1);std::vector<i64> apple(n, 0);auto dfs_break = [&](auto &&self, int v) -> i64 {assert(mark[v] < 0);mark[v] = 1;ans--;i64 ret = apple[v];for (auto nv : gh[v]) {if (nv == par[v] || mark[nv] > 0) continue;ret += self(self, nv);}return ret;};heavy_light_decomposition hld(gh);atcoder::lazy_segtree<i64, op, e, i64, mapping, composition, id> seg(n);rep(i, 0, n) {seg.set(hld.idx(i), d[i]);}i64 res = e();i64 add_val = 0;auto path_add_f = [&](int l, int r) -> void {if (l <= r)seg.apply(l, r, add_val);elseseg.apply(r, l, add_val);};auto path_min_f = [&](int l, int r) -> void {if (l <= r)res = op(res, seg.prod(l, r));elseres = op(res, seg.prod(r, l));};auto path_add = [&](int u, int v, i64 x) -> void {add_val = x;hld.path_noncommutative_query(u, v, false, path_add_f);};auto path_min = [&](int u, int v) -> i64 {res = e();hld.path_noncommutative_query(u, v, false, path_min_f);return res;};while (q--) {int t;std::cin >> t;if (t == 1) {int v;i64 x;std::cin >> v >> x;v--;assert(mark[v] < 0);apple[v] += x;path_add(0, v, -x);if (path_min(0, v) > 0) continue;int ng = 0, ok = hld.distance_from_root(v);while (std::abs(ok - ng) > 1) {int mid = (ok + ng) / 2;if (path_min(v, hld.la(v, mid)) > 0) {ng = mid;} else {ok = mid;}}int broken_v = hld.la(v, ok - 1);i64 sum = dfs_break(dfs_break, broken_v);path_add(broken_v, 0, sum);} else {std::cout << ans << '\n';}}}} // namespace ebiint main() {ebi::fast_io();int t = 1;// std::cin >> t;while (t--) {ebi::main_();}return 0;}