結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-07-01 23:13:03 |
言語 | C++11 (gcc 13.3.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,069 bytes |
コンパイル時間 | 2,345 ms |
コンパイル使用メモリ | 192,428 KB |
実行使用メモリ | 35,916 KB |
最終ジャッジ日時 | 2024-10-12 19:05:43 |
合計ジャッジ時間 | 10,044 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | RE * 16 |
コンパイルメッセージ
main.cpp: In member function ‘long long int Tree::gen_lca()’: main.cpp:100:9: warning: no return statement in function returning non-void [-Wreturn-type] 100 | } | ^ main.cpp: In member function ‘long long int Tree::dfs(const std::vector<std::vector<long long int> >&)’: main.cpp:118:9: warning: no return statement in function returning non-void [-Wreturn-type] 118 | } | ^ main.cpp: In member function ‘bool Tree::verify()’: main.cpp:74:9: warning: control reaches end of non-void function [-Wreturn-type] 74 | } | ^
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for(int i = 0 ; i < (n) ; i++)#define int long long// intを64bit intにしてます!!!template<class T>struct SegmentTree{int n_;vector<T> seg;// [1,N]SegmentTree(int N){n_ = 1;while(n_ < N ) n_ *= 2;seg.resize(2*n_,0); //要設定}void add(int i,int j,int v){i += n_-1;seg[i] = v;i /= 2;while(i){seg[i] = seg[i*2] + seg[i*2+1]; //要設定i /= 2;}}T get(int l,int r,int k,int a,int b){if( b < l || r < a ) return 0; //要設定if( l <= a && b <= r ){return seg[k];}int m = (a+b)/2;return get(l,r,k*2,a,m) + get(l,r,k*2+1,m+1,b); //要設定}inline T get(int l,int r){return get(l,r,1,1,n_);}};class Tree{public://[0,n)int n,logn,root;vector<vector<int>> child;vector<vector<int>> parent;vector<pair<int,int>> edges;vector<int> depth;Tree(int n_,vector<pair<int,int>> es,int root) : root(root){edges = es;n = n_;logn = 0;while(n_){++logn;n_ /= 2;}parent.resize(logn,vector<int>(n,-1));depth.resize(n,-1);child.resize(n);vector<vector<int>> g(n);for( auto e : es ){g[e.first].push_back(e.second);g[e.second].push_back(e.first);}dfs(g);gen_lca();verify();}bool verify(){for(int i = 0 ; i < n ; i++)assert( depth[i] != -1 );}int lca(int x,int y){if( depth[x] < depth[y] )swap(x,y);int d = depth[x] - depth[y];for(int i = 0 ; i < logn ; i++)if( d >> i & 1 ) x = parent[i][x];if( x == y ) return x;for(int i = logn-1 ; i >= 0 ; i--){if( parent[i][x] != parent[i][y] ){x = parent[i][x];y = parent[i][y];}}return parent[0][x];}int distance(int x,int y){return depth[x] + depth[y] - 2 * depth[lca(x,y)];}private:int gen_lca(){for(int i = 1 ; i < logn ; i++){for(int j = 0 ; j < n ; j++)if( parent[i-1][j] != -1 )parent[i][j] = parent[i-1][parent[i-1][j]];}}int dfs(const vector<vector<int>> &g){stack< array<int,3> > S;S.push(array<int,3>{root,-1,0});while( S.size() ){int x = S.top()[0];int p = S.top()[1];int d = S.top()[2];S.pop();parent[0][x] = p;depth[x] = d;for( auto e : g[x] ){if( e != p ){S.push(array<int,3>{e,x,d+1});child[x].push_back(e);}}}}};template<class SegmentTree> class HeavyLightDecomp{public:Tree tr;vector< pair<int,int> > where; // (id,pos)vector< vector<int> > pathSeq;vector<SegmentTree> seg;HeavyLightDecomp(const Tree &tr) : tr(tr){// initwhere.resize(tr.n,{-1,-1});vector<int> subtree(tr.n);vector<pair<int,int>> sortedIdx;for(int i = 0 ; i < tr.n ; i++)sortedIdx.push_back({tr.depth[i],i});sort(sortedIdx.begin(),sortedIdx.end());// calc sizes of each subtreefor(int I = tr.n-1 ; I >= 0 ; I--){int i = sortedIdx[I].second;subtree[i] = 1;for( auto e : tr.child[i] ) subtree[i] += subtree[e];}// do heavyLightDecomp Part1for(int I = 0 ; I < tr.n ; I++){int i = sortedIdx[I].second;if( where[i].first == -1 ){where[i].first = pathSeq.size();pathSeq.push_back(vector<int>());}where[i].second = pathSeq[where[i].first].size();pathSeq[where[i].first].push_back(i);for( auto e : tr.child[i] ){if( 2*subtree[e] > subtree[i] ){where[e].first = where[i].first;}}}// Set segtrees to each heavy-path.for(int i = 0 ; i < pathSeq.size() ; i++){int n_ = 1;while( n_ < pathSeq[i].size() ) n_ *= 2;seg.push_back(SegmentTree(n_));}}//加算点の重複に気をつけてvoid addToVertex(int a,int b,int x){int p = tr.lca(a,b);add(a,p,x,1); //要設定add(b,p,x,0); //要設定}int getToVertex(int a,int b){int p = tr.lca(a,b);return get(a,p,1) + get(b,p,0); //要設定}private:inline void add(int c,int p,int x,int isEdgeQuery){int id1 = where[c].first;int id2 = where[p].first;int l = where[p].second + 1;int r = where[c].second + 1;if( id1 == id2 ){if( l+isEdgeQuery <= r ) seg[id1].add(l+isEdgeQuery,r,x); //要設定}else{seg[id1].add(1,r,x); //要設定add(tr.parent[0][pathSeq[id1][0]],p,x,isEdgeQuery);}}inline int get(int c,int p,int isEdgeQuery){int id1 = where[c].first;int id2 = where[p].first;int l = where[p].second + 1;int r = where[c].second + 1;int ans = 0;if( id1 == id2 ){ans += seg[id1].get(l+isEdgeQuery,r); //要設定}else{ans += seg[id1].get(1,r); //要設定ans += get(tr.parent[0][pathSeq[id1][0]],p,isEdgeQuery);}return ans;}};signed main(){int n;cin >> n;vector< pair<int,int> > es;for(int i = 0 ; i < n - 1 ; i++){int a,b;cin >> a >> b;es.push_back({a,b});}Tree tree(n,es,0);HeavyLightDecomp<SegmentTree<int>> hl(tree);for(int i = 0 ; i < n ; i++){int w;cin >> w;hl.addToVertex(i,i,w);}int q;cin >> q;int ans = 0;for(int i = 0 ; i < q ; i++){int a,b,c;cin >> a >> b >> c;ans += c * hl.getToVertex(a,b);}cout << ans << endl;}