fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using PII = pair<ll, ll>;
  5. #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
  6. #define REP(i, n) FOR(i, 0, n)
  7. #define ALL(x) x.begin(), x.end()
  8. template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
  9. template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
  10. struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
  11. #ifdef DEBUG_ 
  12. #include "../program_contest_library/memo/dump.hpp"
  13. #else
  14. #define dump(...)
  15. #endif
  16. const ll INF = 1LL<<60;
  17.  
  18. template <typename S>
  19. struct sparseTable {
  20.     using T = typename S::T;
  21.     int n;
  22.     vector<int> log2;
  23.     vector<vector<T>> t;
  24.  
  25.     sparseTable() {}
  26.     sparseTable(int nn) { construct(nn); }
  27.     void construct(int nn) {
  28.         n = nn;
  29.         log2.assign(n+1, 0);
  30.         for(int i=2; i<=n; ++i) log2[i] = log2[i >> 1] + 1;
  31.         t = vector<vector<T>>(log2[n]+1, vector<T>(n));
  32.     }
  33.     void init(vector<T> v) {
  34.         for(int i=0; i<n; ++i) t[0][i] = v[i];
  35.         for(int j=1; j<=log2[n]; ++j) {
  36.             int w = 1LL<<(j-1);
  37.             for (int i = 0; i+(w<<1) <= n; ++i) {
  38.                 t[j][i] = S::op(t[j-1][i], t[j-1][i+w]);
  39.             }
  40.         }
  41.     }
  42.     // [l, r]
  43.     T query(int l, int r) {
  44.         int j = log2[r - l];
  45.         return S::op(t[j][l], t[j][r-(1 << j)+1]);
  46.     }
  47. };
  48.  
  49. class LCA {
  50. private:
  51.     const int n = 0;
  52.     const int log2_n = 0;
  53.     vector<vector<int>> par;
  54.     vector<vector<int>> g;
  55.     vector<int> depth;     // 頂点iの深さ
  56.     vector<int> vs;        // 頂点を訪問順に並べたもの
  57.     vector<int> depth_seq; // depth_seq[i] = (頂点vs[i]の深さ)
  58.     vector<int> id;        // 頂点が初めてvsに登場するインデックス
  59.     struct minimum_st {
  60.         using T = PII;
  61.         static T op(const T& a, const T& b) { return min(a, b); }
  62.     }; 
  63.     sparseTable<minimum_st> st;
  64.     void dfs(int v, int p, int d, int &k) {
  65.         id[v] = k; vs[k] = v; depth_seq[k++] = d; depth[v] = d;
  66.         for(auto to: g[v]) if(to != p) {
  67.             dfs(to, v, d+1, k);
  68.             vs[k] = v; depth_seq[k++] = d;
  69.         }
  70.     }
  71. public:
  72.     LCA(int n_=1e5) : n(n_), g(n), depth(n), vs(2*n-1), depth_seq(2*n-1), id(n) {}
  73.     // u-vに辺を張る
  74.     void add_edge(int u, int v) {
  75.         g[u].push_back(v);
  76.         g[v].push_back(u);
  77.     }
  78.     // rootを根として初期化
  79.     void build(int root = 0) {
  80.         int k = 0;
  81.         dfs(root, -1, 0, k);
  82.         vector<PII> v(2*n-1);
  83.         REP(i, 2*n-1) v[i] = {depth_seq[i], i};
  84.         st.construct(2*n-1);
  85.         st.init(v);
  86.     }
  87.     // uとvのlcaを返す O(1)
  88.     int get(int u, int v) {
  89.         if(id[u] > id[v]) swap(u, v);
  90.         return vs[st.query(id[u], id[v]).second];
  91.     }
  92. };
  93.  
  94. int main(void) {
  95.     ll n;
  96.     cin >> n;
  97.     vector<vector<PII>> g(n);
  98.     LCA lca(n);
  99.     REP(i, n-1) {
  100.         ll a, b, c;
  101.         cin >> a >> b >> c;
  102.         a--, b--;
  103.         g[a].emplace_back(b, c);
  104.         g[b].emplace_back(a, c);
  105.         lca.add_edge(a, b);
  106.     }
  107.     lca.build();
  108.  
  109.     vector<ll> sz(n), dead(n);
  110.     auto find_centroid = [&](ll root) {
  111.         auto get_size = [&](auto &&self, ll v, ll p) -> void {
  112.             sz[v] = 1;
  113.             for(auto to: g[v]) if(to.first != p && !dead[to.first]) {
  114.                 self(self, to.first, v);
  115.                 sz[v] += sz[to.first];
  116.             }
  117.         };
  118.         get_size(get_size, root, -1);
  119.         auto dfs = [&](auto &&self, ll v, ll p) -> ll {
  120.             for(auto to: g[v]) if(to.first != p && !dead[to.first]) {
  121.                 if(sz[to.first] > sz[root]/2) return self(self, to.first, v);
  122.             }
  123.             return v;
  124.         };
  125.         return dfs(dfs, root, -1);
  126.     };
  127.  
  128.     vector<ll> par(n);
  129.     auto centroid_decomposition = [&](auto &&self, ll root, ll p) -> void {
  130.         ll c = find_centroid(root);
  131.         dead[c] = true;
  132.         par[c] = p;
  133.         for(auto to: g[c]) if(!dead[to.first]) {
  134.             self(self, to.first, c);
  135.         }
  136.         dead[c] = false;
  137.     };
  138.     centroid_decomposition(centroid_decomposition, 0, -1);
  139.  
  140.     vector<ll> depth(n);
  141.     auto get_depth = [&](auto &&self, ll v, ll p, ll d) -> void {
  142.         depth[v] = d;
  143.         for(auto to: g[v]) if(to.first!=p) {
  144.             self(self, to.first, v, d+to.second);
  145.         }
  146.     };
  147.     get_depth(get_depth, 0, -1, 0);
  148.     auto distance = [&](ll u, ll v) {
  149.         return depth[u] + depth[v] - 2*depth[lca.get(u,v)];
  150.     };
  151.  
  152.     using P = pair<ll,PII>;
  153.     vector<vector<P>> info(n);
  154.     ll q;
  155.     cin >> q;
  156.     REP(i, q) {
  157.         ll type, v;
  158.         cin >> type >> v;
  159.         v--;
  160.         if(type == 1) {
  161.             ll d, c;
  162.             cin >> d >> c;
  163.             ll u = v;
  164.             while(u != -1) {
  165.                 ll dist = d - distance(u, v);
  166.                 if(dist < 0) {
  167.                     u = par[u];
  168.                     continue;
  169.                 }
  170.                 while(info[u].size() && info[u].rbegin()->first <= dist) info[u].pop_back();
  171.                 info[u].push_back({dist, {i, c}});
  172.                 u = par[u];
  173.             }
  174.         } else {
  175.             ll u = v;
  176.             PII ret({-1, 0});
  177.             if(i == q/2) dump(info[u].size());
  178.             while(u != -1) {
  179.                 ll dist = distance(u, v);
  180.                 for(auto j: info[u]) {
  181.                     if(j.first < dist) break;
  182.                     chmax(ret, j.second);
  183.                 }
  184.                 u = par[u];
  185.             }
  186.             cout << ret.second << "\n";
  187.         }
  188.     }
  189.  
  190.     return 0;
  191. }
Runtime error #stdin #stdout #stderr 0s 4476KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/L7986t
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!