結果

問題 No.900 aδδitivee
ユーザー leaf_1415leaf_1415
提出日時 2019-10-04 23:34:12
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 409 ms / 2,000 ms
コード長 6,042 bytes
コンパイル時間 1,371 ms
コンパイル使用メモリ 98,852 KB
実行使用メモリ 42,496 KB
最終ジャッジ日時 2024-10-03 09:47:36
合計ジャッジ時間 10,220 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
9,600 KB
testcase_01 AC 5 ms
9,628 KB
testcase_02 AC 6 ms
9,728 KB
testcase_03 AC 6 ms
9,600 KB
testcase_04 AC 6 ms
9,728 KB
testcase_05 AC 6 ms
9,600 KB
testcase_06 AC 6 ms
9,600 KB
testcase_07 AC 391 ms
31,172 KB
testcase_08 AC 385 ms
31,200 KB
testcase_09 AC 382 ms
31,084 KB
testcase_10 AC 375 ms
31,176 KB
testcase_11 AC 380 ms
31,188 KB
testcase_12 AC 381 ms
31,084 KB
testcase_13 AC 369 ms
31,088 KB
testcase_14 AC 372 ms
31,288 KB
testcase_15 AC 383 ms
31,180 KB
testcase_16 AC 374 ms
31,208 KB
testcase_17 AC 409 ms
31,076 KB
testcase_18 AC 374 ms
31,160 KB
testcase_19 AC 372 ms
31,184 KB
testcase_20 AC 374 ms
31,188 KB
testcase_21 AC 377 ms
31,176 KB
testcase_22 AC 232 ms
42,496 KB
testcase_23 AC 224 ms
42,496 KB
testcase_24 AC 218 ms
42,436 KB
testcase_25 AC 222 ms
42,436 KB
testcase_26 AC 222 ms
42,436 KB
testcase_27 AC 223 ms
42,368 KB
testcase_28 AC 238 ms
42,320 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define llint long long
#define inf 1e18

using namespace std;

struct edge{
	llint to, cost;
	edge(){}
	edge(llint a, llint b){
		to = a, cost = b;
	}
};

typedef pair<int, int> P;

struct HLD{
	int V, logV;
	vector<P> mp;
	map<P, int> mp2;
	vector<P> parent;
	
	//subtree of v is [pre_order[v], back_order[v]]
	vector<int> pre_order;
	vector<int> back_order;
	
	int order;
	int global_id, local_id;
	vector<int> size, depth;
	vector<vector<int> > prev;
	
	HLD(){}
	
	void predfs(vector<int> G[], int v, int p, int d)
	{
		size[v] = 1, depth[v] = d, prev[v][0] = p;
		for(int i = 0; i < G[v].size(); i++){
			if(G[v][i] == p) continue;
			predfs(G, G[v][i], v, d+1);
			size[v] += size[G[v][i]];
		}
	}
	void maindfs(vector<int> G[], int v, int p)
	{
		mp[v] = make_pair(global_id, local_id);
		mp2[make_pair(global_id, local_id)] = v;
		pre_order[v] = ++order;
		
		if(G[v].size() == 1 && G[v][0] == p){
			back_order[v] = order;
			return;
		}
		
		vector<P> vec;
		for(int i = 0; i < G[v].size(); i++){
			if(G[v][i] == p) continue;
			vec.push_back(make_pair(size[G[v][i]], G[v][i]));
		}
		sort(vec.rbegin(), vec.rend());
		
		local_id++;
		if(vec.size() >= 1) maindfs(G, vec[0].second, v);
			
		for(int i = 1; i < vec.size(); i++){
			parent.push_back(mp[v]);
			global_id++, local_id = 0;
			maindfs(G, vec[i].second, v);
		}
		back_order[v] = order;
	}
	int getLCA(int u, int v){
		int x = u, y = v;
		if(depth[y] > depth[x]) swap(x, y);
		
		for(int i = logV-1; i >= 0; i--){
			if(depth[x] - (1<<i) >= depth[y]) x = prev[x][i];
		}
		if(x == y) return x;
		for(int i = logV-1; i >= 0; i--){
			if(prev[x][i] != prev[y][i]){
				x = prev[x][i];
				y = prev[y][i];
			}
		}
		x = prev[x][0];
		return x;
	}
	void pathcalc(int v, int lca, vector<pair<int, P> > &dest)
	{
		int gid = mp[v].first, lid = mp[v].second;
		int Gid = mp[lca].first, Lid = mp[lca].second;
		
		while(Gid != gid){
			dest.push_back(make_pair(gid, make_pair(0, lid)));
			int ngid = parent[gid].first, nlid = parent[gid].second;
			gid = ngid, lid = nlid;
		}
		dest.push_back(make_pair(gid, make_pair(Lid, lid)));
	}
	
	void init(vector<int> G[], int V) // The tree must be 1-indexed.
	{
		this->V = V, logV = 0;
		for(int t = V; t; t/=2) logV++;
		prev.resize(V+1);
		for(int i = 0; i <= V; i++) prev[i].resize(logV);
		
		size.resize(V+1), depth.resize(V+1);
		predfs(G, 1, 0, 0);
		
		prev[0][0] = 0;
		for(int i = 1; i < logV; i++){
			for(int j = 1; j <= V; j++){
				prev[j][i] = prev[prev[j][i-1]][i-1];
			}
		}
		
		mp.resize(V+1), mp2.clear();
		parent.clear(), parent.push_back(make_pair(-1, -1));
		pre_order.resize(V+1), back_order.resize(V+1);
		global_id = local_id = 0, order = 0;
		
		maindfs(G, 1, 0);
	}
	
	void path(int u, int v, vector<pair<int, P> > &dest)
	{
		dest.clear();
		int lca = getLCA(u, v);
		pathcalc(u, lca, dest);
		pathcalc(v, lca, dest);
		
		pair<int, P> p = make_pair(mp[lca].first, make_pair(mp[lca].second, mp[lca].second));
		for(int i = 0; i < dest.size(); i++){
			if(dest[i] == p){
				dest.erase(dest.begin()+i);
				return ;
			}
		}
	}
	
	void getPath(int u, int v, vector<P> &dest) //transform an u-v path into intervals[l, r] on segtree.
	{
		vector<pair<int, P> > src;
		path(u, v, src);
		
		dest.clear();
		for(int i = 0; i < src.size(); i++){
			int u = mp2[make_pair(src[i].first, src[i].second.first)], v = mp2[make_pair(src[i].first, src[i].second.second)];
			dest.push_back(make_pair(pre_order[u], pre_order[v]));
		}
	}
};

// range-add, range-min query
 
struct SegTree{
	int size;
	vector<llint> seg, delay;
	
	SegTree(){}
	SegTree(int size){
		this->size = size;
		seg.resize(1<<(size+1));
		delay.resize(1<<(size+1));
	}
	
	void init()
	{
		for(int i = 0; i < (1<<(size+1)); i++){
			seg[i] = 0;
			delay[i] = 0;
		}
	}
	
	void eval(int l, int r, int k)
	{
		if(delay[k]){
			seg[k] += delay[k] * (r-l+1);
			if(l < r){
				delay[k*2] += delay[k];
				delay[k*2+1] += delay[k];
			}
			delay[k] = 0;
		}
	}
	
	void update(int i, llint val)
	{
		i += (1 << size);
		seg[i] = val;
		while(i > 1){
			i /= 2;
			seg[i] = (seg[i*2] + seg[i*2+1]);
		}
	}
	
	void add(int a, int b, int k, int l, int r, llint val)
	{
		eval(l, r, k);
		
		if(b < l || r < a) return;
		if(a <= l && r <= b){
			delay[k] += val;
			eval(l, r, k);
			return;
		}
		add(a, b, k*2, l, (l+r)/2, val);
		add(a, b, k*2+1, (l+r)/2+1, r, val);
		seg[k] = (seg[k*2] + seg[k*2+1]);
	}
	void add(int a, int b, llint val){
		if(a > b) return;
		add(a, b, 1, 0, (1<<size)-1, val);
	}
 
	llint query(int a, int b, int k, int l, int r)
	{
		eval(l, r, k);
		
		if(b < l || r < a) return 0;
		if(a <= l && r <= b) return seg[k];
		llint lval = query(a, b, k*2, l, (l+r)/2);
		llint rval = query(a, b, k*2+1, (l+r)/2+1, r);
		return (lval + rval);
	}
	llint query(int a, int b)
	{
		return query(a, b, 1, 0, (1<<size)-1);
	}
};

llint n, Q;
vector<int> G[100005];
llint a[100005];
HLD hld;
SegTree seg(17);

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	llint u, v, w;
	for(int i = 1; i <= n-1; i++){
		cin >> u >> v >> w;
		u++, v++;
		G[u].push_back(v);
		a[v] = w;
	}
	
	hld.init(G, n);
	//for(int i = 1; i <= n; i++) cout << hld.pre_order[i] << " "; cout << endl;
	for(int i = 1; i <= n; i++) seg.add(hld.pre_order[i], hld.pre_order[i], a[i]);
	
	cin >> Q;
	llint t, p, x;
	for(int q = 0; q < Q; q++){
		cin >> t;
		if(t == 1){
			cin >> p >> x;
			p++;
			//cout << "! " << hld.pre_order[p] <<  " " << hld.back_order[p] << endl;
			seg.add(hld.pre_order[p], hld.back_order[p], x);
			seg.add(hld.pre_order[p], hld.pre_order[p], -x);
		}
		else{
			cin >> p;
			p++;
			vector<P> vec;
			hld.getPath(1, p, vec);
			
			llint ans = 0;
			for(int i = 0; i < vec.size(); i++){
				//cout << vec[i].first << " " << vec[i].second << endl;
				ans += seg.query(vec[i].first, vec[i].second);
			}
			cout << ans << "\n";
		}
		//for(int i = 1; i <= n; i++) cout << seg.query(i, i) << " "; cout << endl;
		
	}
	flush(cout);
	
	
	return 0;
}
0