結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー | polylogK |
提出日時 | 2019-09-19 23:22:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 853 ms / 3,000 ms |
コード長 | 8,356 bytes |
コンパイル時間 | 2,925 ms |
コンパイル使用メモリ | 205,108 KB |
実行使用メモリ | 32,812 KB |
最終ジャッジ日時 | 2024-10-04 06:26:01 |
合計ジャッジ時間 | 19,521 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 258 ms
32,812 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 6 ms
6,816 KB |
testcase_03 | AC | 6 ms
6,820 KB |
testcase_04 | AC | 7 ms
6,820 KB |
testcase_05 | AC | 6 ms
6,816 KB |
testcase_06 | AC | 7 ms
6,816 KB |
testcase_07 | AC | 739 ms
30,304 KB |
testcase_08 | AC | 756 ms
30,116 KB |
testcase_09 | AC | 816 ms
30,296 KB |
testcase_10 | AC | 748 ms
30,112 KB |
testcase_11 | AC | 770 ms
30,140 KB |
testcase_12 | AC | 655 ms
30,100 KB |
testcase_13 | AC | 643 ms
30,124 KB |
testcase_14 | AC | 644 ms
30,236 KB |
testcase_15 | AC | 651 ms
30,244 KB |
testcase_16 | AC | 636 ms
30,228 KB |
testcase_17 | AC | 845 ms
30,140 KB |
testcase_18 | AC | 834 ms
30,120 KB |
testcase_19 | AC | 829 ms
30,132 KB |
testcase_20 | AC | 853 ms
30,116 KB |
testcase_21 | AC | 845 ms
30,272 KB |
testcase_22 | AC | 455 ms
30,272 KB |
testcase_23 | AC | 436 ms
30,176 KB |
testcase_24 | AC | 460 ms
30,176 KB |
testcase_25 | AC | 438 ms
30,224 KB |
testcase_26 | AC | 446 ms
30,200 KB |
testcase_27 | AC | 571 ms
30,264 KB |
testcase_28 | AC | 560 ms
30,240 KB |
testcase_29 | AC | 560 ms
30,116 KB |
ソースコード
#include <bits/stdc++.h>using namespace std::literals::string_literals;using i64 = long long;using std::cout;using std::endl;using std::cin;template<typename T>std::vector<T> make_v(size_t a){return std::vector<T>(a);}template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}// build: you have to run it before you use// for_each: process [l, r]// for_each_edge: process [l, r]// distance: returns the dist (l, r)class heavy_light_decomposition {using size_type = size_t;using F = std::function<void (int, int)>;public:std::vector<std::vector<int>> g;std::vector<int> vid, inv;private:std::vector<int> head, sz, heavy, par, dep, type;void dfs(int root) {using P = std::pair<int, int>;par[root] = -1;dep[root] = 0;std::stack<P> st;st.push({root, 0});while(!st.empty()) {int v = st.top().first;int & i = st.top().second;if(i < g[v].size()) {int u = g[v][i++];if(u == par[v]) continue;par[u] = v;dep[u] = dep[v] + 1;st.push({u, 0});} else {st.pop();int tmp = 0;for(auto e: g[v]) {if(e == par[v]) continue;sz[v] += sz[e];if(tmp < sz[e]) {tmp = sz[e];heavy[v] = e;}}}}}void bfs(int root, int c, int & k) {std::queue<int> qu({root});while(!qu.empty()) {int h = qu.front(); qu.pop();for(int v = h; v != -1; v = heavy[v]) {type[v] = c;vid[v] = k++;inv[vid[v]] = v;head[v] = h;for(int e: g[v])if(e != par[v] and e != heavy[v]) qu.push(e);}}}public:heavy_light_decomposition() {}heavy_light_decomposition(int n) :g(n), vid(n, -1), head(n), sz(n, 1), heavy(n, -1),par(n), dep(n), inv(n), type(n) {}void add_edge(int a, int b) {g[a].push_back(b);g[b].push_back(a);}void build(std::vector<int> rs = std::vector<int>(1, 0)) {int c = 0, k = 0;for(int r: rs) {dfs(r);bfs(r, c++, k);}}int lca(int u, int v) {while(true) {if(vid[u] > vid[v]) std::swap(u, v);if(head[u] == head[v]) return u;v = par[head[v]];}}void for_each(int u, int v, const F & f) {while(true) {if(vid[u] > vid[v]) std::swap(u, v);f(std::max(vid[head[v]], vid[u]), vid[v]);if(head[u] != head[v]) v = par[head[v]];else break;}}void for_each_edge(int u, int v, const F & f) {while(true) {if(vid[u] > vid[v]) std::swap(u, v);if(head[u] != head[v]) {f(vid[head[v]], vid[v]);v = par[head[v]];} else {if(u != v) f(vid[u] + 1, vid[v]);break;}}}int distance(int u, int v) {return dep[u] + dep[v] - 2 * dep[lca(u, v)];}};template<typename Monoid, typename OperatorMonoid = Monoid>class lazy_segment_tree {using value_type = Monoid;using operator_type = OperatorMonoid;using size_type = size_t;using F = std::function<value_type (value_type, value_type)>;using G = std::function<value_type (value_type, operator_type, int, int)>;using H = std::function<operator_type (operator_type, operator_type)>;size_type size_;size_type height_;F f;G g;H h;value_type id;operator_type id_op;std::vector<value_type> data;std::vector<operator_type> lazy;std::vector<size_type> depth;const size_type get_height(const size_type& size) const {size_type height = 1;while(1 << height < size) height++;return height;}const size_type base_size() const {return 1 << height_;}const value_type reflect(const size_type & k) {if(lazy[k] == id_op) return data[k];int l = (k - (1 << depth[k])) * (base_size() >> depth[k]);int r = l + (base_size() >> depth[k]);return g(data[k], lazy[k], l, r);}void eval(const size_type & k) {if(lazy[k] == id_op) return;lazy[k << 1 ^ 0] = h(lazy[k << 1 ^ 0], lazy[k]);lazy[k << 1 ^ 1] = h(lazy[k << 1 ^ 1], lazy[k]);data[k] = reflect(k);lazy[k] = id_op;}void thrust(const size_type & k) {for(int i = height_; i; i--) eval(k >> i);}void recalc(size_type k) {while(k >>= 1) data[k] = f(reflect(k << 1 ^ 0), reflect(k << 1 ^ 1));}public:lazy_segment_tree() {}lazy_segment_tree(int n, const F & f, const G & g, const H & h, const value_type & id, const operator_type & id_op) :size_(n), f(f), g(g), h(h), id(id), id_op(id_op) {height_ = get_height(size_);data.assign(base_size() << 1, id);lazy.assign(base_size() << 1, id_op);depth.assign(base_size() << 1, 0);for(int i = 0; i < height_ + 1; i++)for(int j = (1 << i); j < (1 << (i + 1)); j++)depth[j] = i;}void update(size_type a, size_type b, operator_type x) {thrust(a += base_size());thrust(b += base_size() - 1);for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if(l & 1) lazy[l] = h(lazy[l], x), l++;if(r & 1) --r, lazy[r] = h(lazy[r], x);}recalc(a);recalc(b);}void change(size_type k, const value_type x) {thrust(k += base_size());data[k] = x;lazy[k] = id_op;recalc(k);}const value_type fold(size_type a, size_type b) {thrust(a += base_size());thrust(b += base_size() - 1);value_type left_value = id;value_type right_value = id;for(size_type l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if(l & 1) left_value = f(left_value, reflect(l++));if(r & 1) right_value = f(reflect(--r), right_value);}return f(left_value, right_value);}const value_type operator[](const size_type & k) {return fold(k, k + 1);}};struct node {int used;int depth;int label;int depth_all;int label_all;node() : used(1), depth(-1), label(-1), depth_all(-1), label_all(-1) {}node(int used, int depth, int label, int depth_all, int label_all) : used(used), depth(depth), label(label), depth_all(depth_all), label_all(label_all) {}void print() {printf("used = %d\n", used);printf("depth = %d\n", depth);printf("label = %d\n", label);printf("depth_all = %d\n", depth_all);printf("label_all = %d\n", label_all);}};int main() {int n; scanf("%d", &n);std::vector<std::vector<std::pair<int, i64>>> g(n);heavy_light_decomposition hld(n);for(int i = 0; i < n - 1; i++) {int a, b, c; scanf("%d%d%d", &a, &b, &c);g[a].push_back({b, c});g[b].push_back({a, c});hld.add_edge(a, b);}hld.build();std::vector<i64> dist(n), depth(n);auto dfs = [&](auto && dfs, int v, int par) -> void {for(auto e: g[v]) {if(e.first == par) continue;dist[e.first] = dist[v] + e.second;depth[e.first] = depth[v] + 1;dfs(dfs, e.first, v);}};dfs(dfs, 0, -1);auto calc = [dist, &hld](int u, int v) {return dist[u] + dist[v] - 2LL * dist[hld.lca(u, v)];};auto f = [](node a, node b) {node ret;ret.used = 0;if(a.depth_all > b.depth_all) {ret.label_all = a.label_all;ret.depth_all = a.depth_all;} else {ret.label_all = b.label_all;ret.depth_all = b.depth_all;}int A = a.label, B = a.depth, C = b.label, D = b.depth;if(a.used) {A = a.label_all;B = a.depth_all;}if(b.used) {C = b.label_all;D = b.depth_all;}if(B > D) {ret.label = A;ret.depth = B;} else {ret.label = C;ret.depth = D;}return ret;};auto gg = [](node a, int b, int l, int r) {if(b) {a.used = 1;a.depth = a.depth_all;a.label = a.label_all;} else {a.used = 0;a.depth = -1;a.label = -1;}return a;};auto h = [](int a, int b) { return b; };lazy_segment_tree<node, int> A(n, f, gg, h, node(), -1);for(int i = 0; i < n; i++) {int v = hld.inv[i];A.change(i, node(0, -1, -1, depth[v], v));}auto kiri = [&A](int l, int r) {A.update(l, r + 1, 1);};auto irik = [&A](int l, int r) {A.update(l, r + 1, 0);};int q; scanf("%d", &q);while(q--) {int k; scanf("%d", &k);std::vector<int> vec(k);for(int i = 0; i < k; i++) scanf("%d", &vec[i]);i64 ans = 0;int c = vec.front();for(auto v: vec) {node tmp = node();auto tanpo = [&](int l, int r) {tmp = f(tmp, A.fold(l, r + 1));};hld.for_each(0, v, tanpo);if(tmp.depth == -1) {ans += calc(v, c);hld.for_each(v, c, kiri);c = hld.lca(v, c);} else {int u = tmp.label;ans += calc(u, v);hld.for_each(u, v, kiri);}}A.update(0, n, 0);printf("%lld\n", ans);}return 0;}