結果

問題 No.386 貪欲な領主
ユーザー kyuridenamidakyuridenamida
提出日時 2016-07-01 23:13:03
言語 C++11
(gcc 11.4.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,069 bytes
コンパイル時間 2,595 ms
コンパイル使用メモリ 178,676 KB
実行使用メモリ 33,000 KB
最終ジャッジ日時 2023-08-02 20:54:12
合計ジャッジ時間 7,223 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘long long int Tree::gen_lca()’:
main.cpp:100:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^
main.cpp: In member function ‘long long int Tree::dfs(const std::vector<std::vector<long long int> >&)’:
main.cpp:118:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^
main.cpp: In member function ‘bool Tree::verify()’:
main.cpp:74:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^

ソースコード

diff # 

#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){
		// init
		where.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 subtree
		for(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 Part1
		for(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;
}
0