fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define FNAME "DIST"
  5. #define xd "\n"
  6. using namespace std;
  7. const int MAXN = (int)2e5 + 10;
  8. const int INF = (int)3e5 + 1;
  9. const long long MOD = (long long)1e9 + 7;
  10.  
  11. template<class X, class Y>
  12. 	bool minimize(X &a , Y b){
  13. 		if(a > b){
  14. 			a = b;
  15. 			return true;
  16. 		}
  17. 		return false;
  18. 	}
  19.  
  20. template<class X, class Y>
  21. 	bool maximize(X &a , Y b){
  22. 		if(a < b){
  23. 			a = b;
  24. 			return true;
  25. 		}
  26. 		return false;
  27. 	}
  28.  
  29. void HuuThien(){
  30. 	ios_base::sync_with_stdio(0);
  31. 	cin.tie(0); cout.tie(0);
  32. 	if(fopen(FNAME".inp","r")){
  33. 		freopen(FNAME".inp","r",stdin);
  34. 		freopen(FNAME".out","w",stdout);
  35. 	}
  36. }
  37.  
  38. struct State{
  39. 	int u, v;
  40. 	long long w;
  41. };
  42.  
  43. vector<int> adj[MAXN];
  44. int n, q;
  45. int parent[MAXN], Size[MAXN], heavy[MAXN];
  46. int pos[MAXN], base[MAXN], depth[MAXN], head[MAXN], timeDFS = 0;
  47. vector<State> edges;
  48.  
  49. void dfs(int u, int par) {
  50. 	Size[u] = 1;
  51. 	heavy[u] = -1;
  52. 	parent[u] = par;
  53. 	depth[u] = (par == -1 ? 0 : depth[par] + 1);
  54. 	int maxnode = 0;
  55.  
  56. 	for(int v : adj[u]) if(v ^ par) {
  57. 		dfs(v, u);
  58. 		Size[u] += Size[v];
  59. 		if(maximize(maxnode, Size[v])) {
  60. 			heavy[u] = v;
  61. 		}
  62. 	}
  63. }
  64.  
  65. void HLD(int u, int h) {
  66. 	head[u] = h;
  67. 	pos[u] = ++timeDFS;
  68.  
  69. 	if(heavy[u] != -1) {
  70. 		HLD(heavy[u], h);
  71. 	}
  72.  
  73. 	for(int v : adj[u]) {
  74. 		if(v == parent[u] || v == heavy[u]) continue;
  75. 		HLD(v, v);
  76. 	}
  77. }
  78.  
  79. namespace SegmentTree{
  80. 	vector<long long> SegTree(4 * MAXN, 0);
  81.  
  82. 	void Update(int node, int l, int r, int ps, long long val) {
  83. 		if(l == r) {
  84. 			SegTree[node] = val;
  85. 			return;
  86. 		}
  87.  
  88. 		int mid = (l + r) / 2;
  89. 		if(ps <= mid) {
  90. 			Update(2 * node, l, mid, ps, val);
  91. 		} else {
  92. 			Update(2 * node + 1, mid + 1, r, ps, val);
  93. 		}
  94.  
  95. 		SegTree[node] = SegTree[2 * node] + SegTree[2 * node + 1];
  96. 	}
  97.  
  98. 	long long getAns(int node, int l, int r, int ql, int qr) {
  99. 		if(l > qr || r < ql) return 0ll;
  100. 		if(ql <= l && r <= qr) return SegTree[node];
  101. 		int mid = (l + r) / 2;
  102. 		long long s1 = getAns(2 * node, l, mid, ql, qr);
  103. 		long long s2 = getAns(2 * node + 1, mid + 1, r, ql, qr);
  104. 		return s1 + s2;
  105. 	}
  106. }
  107.  
  108. long long SumLength(int u, int v) {
  109. 	long long ans = 0;
  110. 	while(head[u] != head[v]) {
  111. 		if(depth[head[u]] < depth[head[v]]) swap(u, v);
  112. 		ans += SegmentTree::getAns(1, 1, n, pos[head[u]], pos[u]);
  113. 		u = parent[head[u]];
  114.  	}	
  115.  
  116. 	if(u ^ v) {
  117. 		if(depth[u] > depth[v]) swap(u, v);
  118. 		ans += SegmentTree::getAns(1, 1, n, pos[u] + 1, pos[v]);
  119. 	}
  120.  
  121. 	return ans;
  122. }
  123.  
  124. void Init() {
  125. 	cin >> n;
  126.  
  127. 	for(int i = 1; i <= n - 1; i++) {
  128. 		int u, v;
  129. 		long long w;
  130. 		cin >> u >> v >> w;
  131. 		adj[u].push_back(v);
  132. 		adj[v].push_back(u);
  133. 		edges.push_back({u, v, w});
  134. 	}
  135.  
  136. 	dfs(1, -1);
  137. 	HLD(1, 1);
  138.  
  139. 	for(int i = 0; i < n - 1 ; i++) {
  140. 		State e = edges[i];
  141. 		int u = e.u, v = e.v;
  142. 		long long wt = e.w;
  143. 		if(parent[u] == v) swap(u, v);
  144. 		SegmentTree::Update(1, 1, n, pos[v], wt);
  145. 	}
  146. } 
  147.  
  148. void Solve() {
  149. 	cin >> q;
  150. 	while(q--) {
  151. 		int type;
  152. 		cin >> type;
  153. 		if(type == 1) {
  154. 			int ps; long long w;
  155. 			cin >> ps >> w;
  156. 			ps--;
  157. 			State e = edges[ps];
  158. 			int u = e.u, v = e.v;
  159. 			if(parent[u] == v) swap(u, v);
  160. 			SegmentTree::Update(1, 1, n, pos[v], w); 
  161. 		} else {
  162. 			int u, v;
  163. 			cin >> u >> v;
  164. 			cout << SumLength(u, v) << xd;
  165. 		}
  166. 	}
  167. }
  168.  
  169. signed main(){
  170. 	HuuThien();	
  171. 	int test = 1;
  172. 	while(test--){
  173. 		Init();
  174. 		Solve();
  175. 	}
  176. }
  177.  
Success #stdin #stdout 0.01s 17864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kK7rE7
language:
C++ (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!