fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. #include <stdio.h>
  4. #define lli long long int
  5. #define pii pair<int,int>
  6. #define plli pair<lli,lli>
  7. #define X first
  8. #define Y second
  9. using namespace std;
  10.  
  11. const int N = 100005;
  12.  
  13. struct Edge
  14. {
  15. 	int x,y;
  16. 	lli c;
  17. 	Edge() {}
  18. 	Edge(int X , int Y , lli C) { x = X , y=  Y , c = C; }
  19.  
  20. 	int other(int p) { return p==x ? y : x; }
  21. } e[N];			// edges
  22. int d[N];		// bottom side of edges
  23.  
  24. int n , q;					// nodes , queries
  25. vector<int> g[N];			// adjacants
  26.  
  27. lli path[N];				// path length from root (=1)
  28. int depth[N];				// depth of nodes
  29.  
  30. int dfsOrder[N] , dfs_i = 0;			// dfsOrder
  31. int start[N] , finish[N];	// start and finish in dfsOrder
  32.  
  33. int euler[N*2] , ei = 1;	// euler tour
  34. int eulerStart[N];			// euler -> first seen of node
  35.  
  36. void dfs(int x , int p , lli w = 0 , int dep = 1)
  37. {
  38. 	// dfs order
  39. 	dfs_i++;
  40. 	dfsOrder[dfs_i] = x;
  41. 	start[x] = dfs_i;
  42.  
  43. 	// node details from root
  44. 	path[x] = w;
  45. 	depth[x] = dep;
  46.  
  47. 	// euler tour
  48. 	euler[ei] = x;
  49. 	eulerStart[x] = ei;
  50. 	ei++;
  51.  
  52. 	for (int i=0 ; i<g[x].size() ; i++)
  53. 	{
  54. 		int y = e[ g[x][i] ].other(x);
  55. 		if (y != p)
  56. 		{
  57. 			d[ g[x][i] ] = y;	// bottom side of this edge
  58. 			dfs(y , x , w + e[ g[x][i] ].c , dep+1);
  59.  
  60. 			euler[ei] = x;	// euler tour
  61. 			ei++;
  62. 		}
  63. 	}
  64.  
  65. 	// dfs order
  66. 	finish[x] = dfs_i;
  67. }
  68.  
  69. lli st[4*N];		// segment tree
  70. int stPos[N];		// position of nodes in segment tree
  71. struct SegmentTree
  72. {
  73. 	int mp;
  74.  
  75. 	SegmentTree() {}
  76.  
  77. 	void init()
  78. 	{
  79. 		mp = 0;
  80. 		init( 1 , 1 , n );
  81. 	}
  82.  
  83. 	void init(int p , int i , int j)
  84. 	{
  85. 		mp = max(mp , p);
  86. 		if (i==j)
  87. 		{
  88. 			st[p] = path[dfsOrder[i]];
  89. 			stPos[dfsOrder[i]] = p;
  90. 			return;
  91. 		}
  92. 		int m = (i+j)/2 , l = p*2 , r = l+1;
  93. 		init(l , i , m);
  94. 		init(r , m+1 , j);
  95. 	}
  96.  
  97. 	void update(int i, lli c)
  98. 	{
  99. 		update(1 , 1 , n , start[i] , finish[i] , c);
  100. 	}
  101.  
  102. 	void update(int p, int i ,int j , int L , int R , lli c)
  103. 	{
  104. 		if (j<L || i>R) return;
  105. 		if (i>=L && j<=R)
  106. 		{
  107. 			st[p] += c;
  108. 			return ;
  109. 		}
  110. 		int m = (i+j)/2 , l = p*2 , r = l+1;
  111. 		update(l , i , m , L , R , c);
  112. 		update(r , m+1 , j , L , R , c);
  113. 	}
  114.  
  115. 	lli get(int i)
  116. 	{
  117. 		int p = stPos[i];
  118. 		lli sum = 0;
  119. 		while (p)
  120. 		{
  121. 			sum += st[p];
  122. 			p/=2;
  123. 		}
  124. 		return sum;
  125. 	}
  126. };
  127.  
  128. int sp[2*N][20];		// sparse table for finding LCA from euler tour
  129. struct SparseTable
  130. {
  131. 	int sn;
  132. 	SparseTable() {}
  133.  
  134. 	void init(int _n)
  135. 	{
  136. 		sn = _n;
  137. 		for (int i=1 ; i<=sn ; i++) sp[i][0] = i;
  138.  
  139. 		for (int j=1,k=2 ; k<=sn ; j++,k*=2)
  140. 		{
  141. 			for (int i=1 ; i<=sn-k+1 ; i++)
  142. 			{
  143. 				int l = sp[i][j-1];
  144. 				int r = sp[i+k/2][j-1];
  145. 				sp[i][j] = depth[ euler[l] ] < depth[ euler[r] ] ? l : r;
  146. 			}
  147. 		}
  148. 	}
  149.  
  150. 	int get(int i , int j)
  151. 	{
  152. 		int dis = j-i+1;
  153. 		int lg = log2(dis);
  154. 		int p = 1<<lg;
  155. 		int l = sp[i][lg] , r = sp[j-p+1][lg];
  156. 		return depth[ euler[l] ] < depth[ euler[r] ] ? euler[l] : euler[r];
  157. 	}
  158. };
  159.  
  160. void pout(int x)
  161. {
  162. 	cout<<x<<(x<10 ? " " : "")<<" ";
  163. }
  164.  
  165. int main()
  166. {
  167. 	ios_base::sync_with_stdio(false);
  168.  
  169. 	cin>>n;
  170. 	for (int i = 1 ; i<=n-1 ; i++)
  171. 	{
  172. 		int x,y,c;
  173. 		cin>>x>>y>>c;
  174. 		e[i] = Edge(x,y,c);
  175. 		g[x].push_back(i);
  176. 		g[y].push_back(i);
  177. 	}
  178. 	dfs(1 , 1);
  179.  
  180. 	SegmentTree seg;
  181. 	seg.init();
  182.  
  183. 	SparseTable sps;
  184. 	sps.init(ei-1);
  185.  
  186. 	cin>>q;
  187. 	while (q--)
  188. 	{
  189. 		int w;
  190. 		lli x ,y;
  191. 		cin>>w>>x>>y;
  192.  
  193. 		if (w==1)
  194. 		{
  195. 			lli dif = y - e[x].c;
  196. 			e[x].c = y;
  197. 			seg.update(d[x] , dif);
  198. 		}
  199. 		else if (w==2)
  200. 		{
  201. 			int esx = eulerStart[x] , esy = eulerStart[y];
  202. 			if ( esy < esx )
  203. 			{
  204. 				swap(x , y);
  205. 				swap(esx , esy);
  206. 			}
  207. 			int lca = sps.get(esx , esy);
  208. 			lli ans = seg.get(x) + seg.get(y) - 2LL*seg.get(lca);
  209. 			cout<<ans<<"\n";
  210. 		}
  211. 	}
  212.  
  213.     return 0;
  214. }
  215.  
Runtime error #stdin #stdout 0s 37304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ltyDQ7
language:
C++14 (gcc 8.3)
created:
8 years 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!