結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-07-09 00:13:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 260 ms / 2,000 ms |
コード長 | 9,813 bytes |
コンパイル時間 | 1,386 ms |
コンパイル使用メモリ | 116,596 KB |
実行使用メモリ | 23,564 KB |
最終ジャッジ日時 | 2024-10-13 07:47:14 |
合計ジャッジ時間 | 3,557 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
/*### ############## ################################################################################################################################################ ##################################### ####### ############################ ################# ################### # ########################## ######### ################################### # ########################### ############## ################################ ######### ################################### ####### ###################################### # ####### ################################################ ################################################ ################################################ ############################################## ########################################## ################################# ######################### ################ ######## ### ## # ## # # # # # #### #### #### #### ##### # # # # ## # # # # # # #____# ### #/ # # ## # # # # # # # #^^^^ ### ###/# # # # #### #### ###/# #### ####*/#include <iostream>#include <vector>#include <cstdio>#include <sstream>#include <map>#include <string>#include <algorithm>#include <queue>#include <cmath>#include <functional>#include <set>#include <ctime>#include <random>#include <chrono>#include <cassert>using namespace std;namespace {using Integer = long long; //__int128;template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}template<class T> istream& operator , (istream& is, T& val){ return is >> val;}template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}template<class T> ostream& operator , (ostream& os, const T& val){ return os << " " << val;}template<class H> void print(const H& head){ cout << head; }template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }template<class H> void eprint(const H& head){ cerr << head; }template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }class range{long long start_, end_, step_;public:struct range_iterator{long long val, step_;range_iterator(long long v, long long step) : val(v), step_(step) {}long long operator * (){return val;}void operator ++ (){val += step_;}bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;}};range(long long len) : start_(0), end_(len), step_(1) {}range(long long start, long long end) : start_(start), end_(end), step_(1) {}range(long long start, long long end, long long step) : start_(start), end_(end), step_(step) {}range_iterator begin(){ return range_iterator(start_, step_); }range_iterator end(){ return range_iterator( end_, step_); }};string operator "" _s (const char* str, size_t size){ return move(string(str)); }constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexedmt19937 mt(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count());template<class T> string join(const vector<T>& v, const string& sep){stringstream ss; for(int i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str();}string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }}constexpr long long mod = 9_ten + 7;//HL分解 構築O(|v|), 空間O(|v|)class HeavyLightDecomposition{public:struct heavy_set{vector<int> element;int depth;int parent_vertex;heavy_set(int v, int d, int par) : element(1,v), depth(d), parent_vertex(par){}};vector<vector<int>>& G;vector<heavy_set> S;vector<int> subtree_size;vector<int> set_index;vector<int> ele_index;private:int get_subtree_size(int pos, int par){int sz = 1;for(int ch : G[pos]){if(ch == par) continue;sz += get_subtree_size(ch, pos);}return subtree_size[pos] = sz;}void make_path(int pos, int par, int set_id){set_index[pos] = set_id;ele_index[pos] = S[set_id].element.size()-1;int largest_child = -1;int value = 0;for(int ch : G[pos]){if(ch == par) continue;if(value < subtree_size[ch]){value = subtree_size[ch];largest_child = ch;}}for(int ch : G[pos]){if(ch == par) continue;if(largest_child == ch){S[set_id].element.push_back(ch);make_path(ch, pos, set_id);}else{S.emplace_back( ch, S[set_id].depth+1, pos );make_path(ch, pos, S.size()-1);}}}void init(int root){subtree_size.resize(G.size(), 0);get_subtree_size(root,root);set_index.resize(G.size(), 0);ele_index.resize(G.size(), 0);S.emplace_back( root,0,root );make_path( root, root, 0 );subtree_size.clear();}public:HeavyLightDecomposition(vector<vector<int>>& G_, int root = 0) : G(G_){init(root);}//set_index, element_index//S[set_index].element[element_index] == vpair<int,int> get_position(int v){return {set_index[v], ele_index[v]};}};//Lowest Common Ancestor with HL-decomposition tree//O(log n) / queryint LCA(HeavyLightDecomposition& T, int u, int v){auto pu = T.get_position(u);auto pv = T.get_position(v);if(pu.first == pv.first){return pu.second < pv.second ? u : v;}if(T.S[pu.first].depth > T.S[pv.first].depth){swap(pu, pv);swap(u,v);}while(T.S[pu.first].depth != T.S[pv.first].depth){v = T.S[pv.first].parent_vertex;pv = T.get_position( v );}while(pu.first != pv.first){u = T.S[pu.first].parent_vertex;v = T.S[pv.first].parent_vertex;pu = T.get_position(u);pv = T.get_position(v);if(T.S[pv.first].depth == 0) break;if(T.S[pv.first].depth == 0) break;}if(pu.first == pv.first){return pu.second < pv.second ? u : v;}else{abort();}return -1;}void Euler_tour(vector<vector<int>>& G, int pos, int last, vector<int>& res){res.push_back(pos);for(int nx : G[pos]){if(nx == last) continue;Euler_tour(G, nx, pos, res);}res.push_back(pos);}int main(){int n;cin >> n;vector<vector<int>> G(n);for(int i :range(n-1)){int a,b;cin >> a,b;G[a].push_back(b);G[b].push_back(a);}vector<int> u(n);cin >> u;HeavyLightDecomposition t(G, 0);vector<int> e;Euler_tour(G, 0, 0, e);vector<int> o(n, 1e8);vector<int> s(e.size(), 0);for(int i=0; i<e.size(); i++){o[e[i]] = min(o[e[i]], i);if( o[e[i]] == i){s[i] = +u[e[i]];}else{s[i] = -u[e[i]];}}for(int i=1; i<s.size(); i++){s[i] += s[i-1];}long long ans = 0;int m;cin >> m;while(m--){int a,b,c;cin >> a,b,c;int p = o[LCA(t, a,b)];int w = o[a];int v = o[b];if(w>v) swap(w,v);long long tmp = 0;tmp += s[w] - (p==0 ? 0 : s[p-1]);tmp += s[v] - s[p];ans += tmp * c;}println(ans);return 0;}