#34522 (C++11) No.235 めぐるはめぐる (5)

提出ソース

結果

問題	No.235 めぐるはめぐる (5)
ユーザー	koyumeishi
提出日時	2015-06-27 01:52:40
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	1,069 ms / 10,000 ms
コード長	9,775 bytes
コンパイル時間	1,279 ms
コンパイル使用メモリ	109,016 KB
実行使用メモリ	98,000 KB
最終ジャッジ日時	2024-07-07 19:51:31
合計ジャッジ時間	5,572 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,069 ms 89,728 KB
testcase_01	AC	577 ms 98,000 KB
testcase_02	AC	863 ms 91,344 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:465:25: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type*’ {aka ‘long long int*’} [-Wformat=]
  465 |                 scanf("%d", &s[i]);
      |                        ~^
      |                         |
      |                         int*
      |                        %lld
main.cpp:469:25: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type*’ {aka ‘long long int*’} [-Wformat=]
  469 |                 scanf("%d", &c[i]);
      |                        ~^
      |                         |
      |                         int*
      |                        %lld
main.cpp:461:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  461 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:465:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  465 |                 scanf("%d", &s[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:469:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  469 |                 scanf("%d", &c[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:475:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  475 |                 scanf("%d%d", &a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~~
main.cpp:484:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  484 |         scanf("%d", &q);

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

#define MOD 1000000007

vector<long long> s, c;

class LCA{

	int root;
	//depth of node[i]
	vector<int> d;
	
	//parent of node[i]
	vector<vector<int> > p;

	
	int log_n;
	
	//initialization of depths and parents
	void init(vector<vector<int> > &g, int pos, int last, int v){
		d[pos] = v;
		p[0][pos] = last;
		for(int i=0; i<g[pos].size(); i++){
			if(g[pos][i] == last) continue;
			init(g, g[pos][i], pos, v+1);
		}
	}

public:

	//vector<vector<int> >
	//g[i][j] := node[i]'s edge gose to node[ g[i][j] ]
	
	LCA(vector<vector<int> > &g, int r){
		int n = g.size();
		root = r;
		d = vector<int>(n);
		log_n = 1;
		while(1LL<<log_n <= n) log_n++;
		p = vector<vector<int> >(log_n, vector<int>(n));
		
		init(g, root,-1,0);
		
		for(int k=0; k+1 < log_n; k++){
			for(int v=0; v<n; v++){
				if(p[k][v] < 0) p[k+1][v] = -1;
				else p[k+1][v] = p[k][p[k][v]];
			}
		}
	}
	
	LCA(vector<vector<int> > &g){
		int n = g.size();
		root = 0;
		d = vector<int>(n);
		log_n = 1;
		while(1LL<<log_n <= n) log_n++;
		p = vector<vector<int> >(log_n, vector<int>(n));

		//initialize as root = 0
		init(g, root,-1,0);
		
		for(int k=0; k+1 < log_n; k++){
			for(int v=0; v<n; v++){
				if(p[k][v] < 0) p[k+1][v] = -1;
				else p[k+1][v] = p[k][p[k][v]];
			}
		}
	}
	
	//return the node number of lowest common ancestor between u and v
	int get_lca(int u, int v){
		if(d[u] > d[v]) swap(u,v);
		for(int k=0; k<log_n; k++){
			if( (d[v] - d[u]) >> k & 1){
				v = p[k][v];
			}
		}
		if(u==v) return u;

		for(int k=log_n-1; k>=0; k--){
			if(p[k][u] != p[k][v]) {
				u = p[k][u];
				v = p[k][v];
			}
		}
		return p[0][u];
	}

	//return depth of node[u]
	int depth(int u){
		return d[u];
	}
};

struct my_value{
	long long c;
	long long val;
	my_value(): c(0), val(0){
	}
	my_value(long long c_, long long val_) : c(c_), val(val_){
	}
};


template<class T=my_value, class V=long long>
class Segment_Tree_Lazy{
private:
	//default values are set in the constractor
	const T default_value;		//default (NULL) node value
	const V default_lazy_value;	//default lazy value

	struct node{
		T value; V lazy_value;
		bool lazy; int lb; int ub;
		node* par; node* lch; node* rch;

		node(T default_value, V default_lazy_value) : 
			value(default_value),
			lazy_value(default_lazy_value),
			lazy(false),
			lb(0),ub(0),
			par(NULL),lch(NULL),rch(NULL){
		}
	};


	T evaluate(T left_val, T right_val){
		return my_value((left_val.c + right_val.c)%MOD, (left_val.val + right_val.val)%MOD);
	}

	void new_lazy(node* t, V z){	
		if(t==NULL) return;
		if(t->lazy){
			t->lazy_value = (t->lazy_value + z)%MOD;
		}else{
			t->lazy_value = z;
		}
		t->lazy = true;
	}

	T get_value(node* t){
		if(t==NULL) return default_value;
		if(t->lazy) return T(t->value.c , (t->value.val + (t->lazy_value * t->value.c)%MOD) % MOD);
		return t->value;
	}

	vector<node> v;
	node* root;

	int size;

	node* constract(node* t, int pos, int lb, int ub){
		if(pos == 0){
			t->par = t;
		}
		t->lb = lb;
		t->ub = ub;

		if(pos<size-1){
			t->lch = constract(&v[(pos<<1) + 1], (pos<<1) + 1, lb, (ub+lb)>>1);
			t->lch->par = t;

			t->rch = constract(&v[(pos<<1) + 2], (pos<<1) + 2, (ub+lb)>>1, ub);
			t->rch->par = t;
		}

		return t;
	}

	void initialize(int size_){
		size = 1;
		while(size < size_) size <<= 1;

		v = vector<node>(size<<1, node(default_value, default_lazy_value));
		root = constract(&v[0], 0, 0, size);
	}

	//propagate lazy value of node t to its children
	void push(node* t){
		if(t==NULL) return;
		if(t->lazy){
			if(t->lch != NULL){	//has child
				new_lazy(t->lch, t->lazy_value);
				new_lazy(t->rch, t->lazy_value);

				t->value = evaluate( get_value(t->lch), get_value(t->rch) );
			}else{
				t->value = get_value(t);
			}

			t->lazy_value = default_lazy_value;
			t->lazy = false;
		}
	}


	void range_add(int left, int right, V z, node* t){
		if(t==NULL) return;
		if(t->ub <= left || right <= t->lb){
			return;
		}

		push(t);
		if(left <= t->lb && t->ub <= right){
			new_lazy(t, z);
			return;
		}

		//partialy covered
		range_add(left, right, z, t->lch);
		range_add(left, right, z, t->rch);
		
		t->value = evaluate( get_value(t->lch), get_value(t->rch) );
	}

	//get value of [left,right)
	T get_range_value(int left, int right, node* t){
		if(t==NULL) return default_value;
		if(t->ub <= left || right <= t->lb){
			return default_value;
		}

		push(t);
		if(left <= t->lb && t->ub <= right){
			return get_value(t);
		}

		T L = get_range_value(left, right, t->lch);
		T R = get_range_value(left, right, t->rch);

		return evaluate(L, R);
	}

public:
	//default node value must be set
	// sum : 0
	// max : MIN_INF
	// min : MAX_INF
	// gcd : 1
	Segment_Tree_Lazy(int size_) : 
		default_value(T()), default_lazy_value(0LL){
		initialize(size_);
	}

	Segment_Tree_Lazy() : 
		default_value(T()), default_lazy_value(0LL){
	}

	void resize(int sz){
		initialize(sz);
	}


	//node[pos] <= new_value
	void update(int pos, T new_value){
		node* t = &v[pos + size-1];

		t->value = new_value;

		while(t != root){
			t = t->par;
			t->value = evaluate( get_value(t->lch), get_value(t->rch) );
		}
	}

	//[l,r) += add_value
	void range_add(int left, int right, V z){
		range_add(left, right, z, root);
	}

	//get value [left,right)
	T get_range_value(int left, int right){
		return get_range_value(left, right, root);
	}

	void dbg(){
		for(int i=0; i<v.size(); i++){
			cerr << get_value(&v[i]) << " ";
		}
		cerr << endl;
	}
};

class HL_Decomposition{
	class decomposited_node{
	public:
		Segment_Tree_Lazy<my_value, long long> seg;
		int size;
		int root;
		decomposited_node(){}
		decomposited_node(int size_, int root_) : 
			seg(size_), size(size_), root(root_){
		}
	};

	class info{
	public:
		decomposited_node* node;
		int pos;
		info():node(NULL){}

	};

	int sub_tree_dfs(int pos, int par){
		parent[pos] = par;
		int ret = 1;
		for(int i=0; i<G[pos].size(); i++){
			int to = G[pos][i];
			if(to == par) continue;
			ret += sub_tree_dfs(to, pos);
		}
		sub_tree_size[pos] = ret;
		return ret;
	}

public:
	int n;
	vector<vector<int>> G;
	vector<int> parent;

	vector<int> sub_tree_size;
	vector<info> information;

	vector<vector<int>> decomposited_tree;

	vector<decomposited_node> dec_nodes;

	LCA lca;

	HL_Decomposition(vector<vector<int>>& G, int root = 0) : 
	n(G.size()), sub_tree_size(G.size()), information(G.size()), lca(G,root), parent(G.size()){
		this->G = G;
		sub_tree_dfs(0,0);

		vector<bool> visit(n, false);
		queue<int> head;
		
		head.push(0);
		while(head.size()){
			int pos = head.front();
			decomposited_tree.push_back({pos});
			head.pop();

			visit[pos] = true;

			while(true){
				int max_size = 0;
				int next = -1;
				for(int i=0; i<G[pos].size(); i++){
					int to = G[pos][i];
					if(visit[to]) continue;
					if(max_size < sub_tree_size[to]){
						if(next>=0){
							head.push(next);
						}

						max_size = sub_tree_size[to];
						next = to;
					}else{
						head.push(to);
					}
				}

				if(next < 0) break;
				decomposited_tree.back().push_back(next);
				visit[next] = true;
				pos = next;
			}
		}

		dec_nodes.resize(decomposited_tree.size());
		for(int i=0; i<decomposited_tree.size(); i++){
			dec_nodes[i].size = decomposited_tree[i].size();
			dec_nodes[i].root = decomposited_tree[i][0];
			dec_nodes[i].seg.resize(dec_nodes[i].size);

			for(int j=0; j<decomposited_tree[i].size(); j++){
				int pos = decomposited_tree[i][j];
				information[pos].node = &dec_nodes[i];
				information[pos].pos = j;

				dec_nodes[i].seg.update(j, my_value(c[pos], s[pos]));

				//cerr <<"{ " << c[pos] << ", " << s[pos] << " }, ";
			}
			//cerr << endl;
		}
	}

	long long query_get_val(int pos, int lca_, int type){
		decomposited_node* t = information[pos].node;
		if(t != information[lca_].node){
			long long ret = 0;
			int l = 0;
			int r = information[pos].pos+1;
			ret = t->seg.get_range_value(l, r).val;
			ret += query_get_val(parent[t->root], lca_, type);
			ret %= MOD;
			return ret;

		}else{
			int l = information[lca_].pos;
			int r = information[pos].pos+1;
			if(type == 1) l += 1;
			return t->seg.get_range_value(l, r).val;
		}
	}

	long long query_get(int x, int y){
		int lca_ = lca.get_lca(x,y);

		long long ret = 0;
		ret += query_get_val(x, lca_, 0);
		ret += query_get_val(y, lca_, 1);
		ret %= MOD;

		return ret;
	}


	void query_set_val(int pos, int lca_, int type, long long z){
		decomposited_node* t = information[pos].node;
		if(t != information[lca_].node){
			int l = 0;
			int r = information[pos].pos+1;
			t->seg.range_add(l, r, z);
			query_set_val(parent[t->root], lca_, type, z);

		}else{

			int l = information[lca_].pos;
			int r = information[pos].pos+1;
			if(type == 1) l += 1;
			t->seg.range_add(l, r, z);
		}
	}

	void query_set(int x, int y, long long z){
		int lca_ = lca.get_lca(x,y);
		query_set_val(x, lca_, 0, z);
		query_set_val(y, lca_, 1, z);
	}
};




int main(){
	int n;
	scanf("%d", &n);
	s.resize(n);
	c.resize(n);
	for(int i=0; i<n; i++){
		scanf("%d", &s[i]);
	}

	for(int i=0; i<n; i++){
		scanf("%d", &c[i]);
	}

	vector<vector<int>> G(n);
	for(int i=0; i<n-1; i++){
		int a,b;
		scanf("%d%d", &a,&b);
		a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	HL_Decomposition hld(G, 0);

	int q;
	scanf("%d", &q);
	while(q--){
		int type;
		scanf("%d", &type);
		if(type == 0){
			int x,y,z;
			scanf("%d%d%d", &x, &y, &z);
			x--;
			y--;
			hld.query_set(x,y,z);

		}else if(type == 1){
			int x,y;
			scanf("%d%d", &x, &y);

			x--;
			y--;
			long long val = hld.query_get(x,y)%MOD;
			printf("%lld\n", val);


		}
	}
	return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード