fork(2) download
copy 
  1. //itisalways42
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long int 	LL;
  7. typedef pair<LL,LL>   II;
  8. typedef vector< II >      VII;
  9. typedef vector<int>     VI;
  10. typedef vector< VI > 	VVI;
  11.  
  12. #define PB push_back
  13. #define MP make_pair
  14. #define F first
  15. #define S second
  16. #define SZ(a) (int)(a.size())
  17. #define ALL(a) a.begin(),a.end()
  18. #define SET(a,b) memset(a,b,sizeof(a))
  19.  
  20. #define si(n) scanf("%d",&n)
  21. #define dout(n) printf("%d\n",n)
  22. #define sll(n) scanf("%lld",&n)
  23. #define lldout(n) printf("%lld\n",n)
  24. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  25.  
  26. #define TRACE
  27.  
  28. #ifdef TRACE
  29. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  30. template <typename Arg1>
  31. void __f(const char* name, Arg1&& arg1){
  32. 	cerr << name << " : " << arg1 << std::endl;
  33. }
  34. template <typename Arg1, typename... Args>
  35. void __f(const char* names, Arg1&& arg1, Args&&... args){
  36. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  37. }
  38. #else
  39. #define trace(...)
  40. #endif
  41.  
  42.  
  43. const int N = int(1e5)+10;
  44. const int LOGN = 20;
  45. VII g[N],tree[N];
  46. int Q[N],arr[N],dep[N],lev[N];
  47. int Time,n;
  48. LL initDist[N],currDist[N];
  49. LL Bit[N],parEdge[N];
  50. int Par[LOGN][N];
  51.  
  52. void add(int x, LL val)
  53. {
  54. 	while(x<N)
  55. 	{
  56. 		Bit[x] += val;
  57. 		x += x&(-x);
  58. 	}
  59. }
  60.  
  61. LL query(int x)
  62. {
  63. 	LL ret=0;
  64. 	while(x)
  65. 	{
  66. 		ret += Bit[x];
  67. 		x -= x&(-x);
  68. 	}
  69. 	return ret;
  70. }
  71.  
  72. void dfs0(int u=0, int p=0, LL d=0, int h=0)
  73. {
  74. 	Par[0][u] = p;
  75. 	initDist[u] = d;
  76. 	arr[u] = Time++;
  77. 	lev[u] = h;
  78. 	for(int i=0; i<SZ(g[u]); i++)
  79. 		if(g[u][i].F != p)
  80. 		{
  81. 			parEdge[g[u][i].F] = g[u][i].S;
  82. 			dfs0(g[u][i].F,u,d+g[u][i].S,h+1);
  83. 		}
  84. 	dep[u] = Time;
  85. }
  86.  
  87. void precompute()
  88. {
  89. 	Time = 1;
  90. 	dfs0();
  91. 	for(int i=1; i<LOGN; i++)
  92. 		for(int j=0; j<n; j++)
  93. 			Par[i][j] = Par[i-1][Par[i-1][j]];
  94. 	// arrange nodes in order of arrival time
  95. 	vector<II> v;
  96. 	for(int i=0; i<n; i++) v.PB(MP(arr[i],i));
  97. 	sort(ALL(v));
  98. 	// build Fenwick tree where sum upto index i is distance from node i-1 to node 0 (root)
  99. 	add(1,initDist[v[0].S]);
  100. 	for(int i=1; i<SZ(v); i++) add(i+1,initDist[v[i].S]-initDist[v[i-1].S]);
  101. }
  102.  
  103. int lca(int u, int v)
  104. {
  105. 	if(lev[u] < lev[v]) swap(u,v);
  106. 	for(int i=LOGN-1; i>=0; i--)
  107. 		if(lev[Par[i][u]] >= lev[v])
  108. 			u = Par[i][u];
  109. 	if(u==v) return u;
  110. 	for(int i=LOGN-1; i>=0; i--)
  111. 		if(Par[i][u] != Par[i][v])
  112. 			u = Par[i][u], v = Par[i][v];
  113. 	return Par[0][u];
  114. }
  115.  
  116. LL dist(int u, int p)
  117. {
  118. 	if(lev[u] < lev[p]) swap(u,p);
  119. 	return currDist[u] - currDist[p];
  120. }
  121.  
  122. //Q[]: array containing k nodes of auxillary tree
  123. //arr[] : arrival time of nodes
  124. //dep[] : departure time of nodes
  125. //anc(p,u) : returns true if p is ancestor of u
  126. //VI tree[N] : final auxillary tree with O(k) nodes
  127. bool anc(int p, int u)
  128. {
  129. 	return arr[p] < arr[u] && dep[p] >= dep[u];
  130. }
  131. bool cmp(int u,int v)
  132. {
  133. 	return arr[u]<arr[v];
  134. }
  135. int create_tree(int k)
  136. {
  137. 	//return root of tree
  138. 	set<int> S;
  139. 	//get distinct nodes 
  140. 	for(int i=0;i<k;i++)S.insert(Q[i]);k=0;
  141. 	for(auto it=S.begin();it!=S.end();it++)Q[k++]=*it;
  142. 	sort(Q,Q+k,cmp);
  143. 	int kk = k;
  144. 	//distinct initial nodes, add lca of adjacent pairs
  145. 	for(int i=0;i<kk-1;i++)
  146. 	{
  147. 		int x = lca(Q[i],Q[i+1]);
  148. 		if(S.count(x)) continue;
  149. 		Q[k++]=x;
  150. 		S.insert(x);
  151. 	}
  152. 	sort(Q,Q+k,cmp);
  153. 	//get latest distance from each node in set S to root
  154. 	for(int i=0; i<k; i++) currDist[Q[i]] = query(arr[Q[i]]);
  155. 	//clear tree vector of every node in auxillary tree
  156. 	for(int i=0; i<k; i++) tree[Q[i]].clear();
  157. 	stack<int> s;
  158. 	//Q[0] is root of auxillary tree as it has min arrival time
  159. 	s.push(Q[0]);
  160. 	for(int i=1;i<k;i++)
  161. 	{
  162. 		// find parent of Q[i] in auxillary tree
  163. 		while(!anc(s.top(),Q[i])) s.pop();
  164. 		// add edge with currDist
  165. 		LL d = dist(Q[i],s.top());
  166. 		tree[s.top()].PB(MP(Q[i],d));
  167. 		tree[Q[i]].PB(MP(s.top(),d));
  168. 		s.push(Q[i]);
  169. 	}
  170. 	return Q[0];
  171. }
  172.  
  173. void updateEdge(int u, int v, LL val)
  174. {
  175. 	if(anc(u,v)) swap(u,v);
  176. 	// update edge from u to v where v = par(u) from parEdge[u] to val
  177. 	// this edge affects distance of every node in subtree of u which is the range [arr[u],dep[u]]
  178. 	// hence update Fenwick tree at arr[u] and dep[u]+1
  179. 	LL diff = val - parEdge[u];
  180. 	parEdge[u] = val;
  181. 	add(arr[u],diff);
  182. 	add(dep[u],-diff);
  183. }
  184.  
  185. LL ans[N],d1[N],d2[N];
  186. void dfs(int u, int p)
  187. {
  188. 	// d1[u] and d2[u] denote the farthest and 2nd farthest leafs in subtree of u through 2 different children
  189. 	d1[u] = 0; d2[u] = 0;
  190. 	for(int i=0; i<SZ(tree[u]); i++)
  191. 	{
  192. 		int v = tree[u][i].F;
  193. 		LL w = tree[u][i].S;
  194. 		if(v == p) continue;
  195. 		dfs(v,u);
  196. 		if(d1[v] + w > d1[u])
  197. 		{
  198. 			d2[u] = d1[u];
  199. 			d1[u] = d1[v] + w;
  200. 		}
  201. 		else if(d1[v] + w > d2[u])
  202. 			d2[u] = d1[v] + w;
  203. 	}
  204. }
  205.  
  206. void dfs1(int u, int p)
  207. {
  208. 	// d1[u] and d2[u] denote the farthest and 2nd farthest leafs in subtree of u through 2 different children
  209. 	// when considering u as root of auxillary tree
  210. 	ans[u] = d1[u];
  211. 	for(int i=0; i<SZ(tree[u]); i++)
  212. 	{
  213. 		int v = tree[u][i].F;
  214. 		LL w = tree[u][i].S;
  215. 		LL val = d1[u];
  216. 		II tmp = MP(d1[v],d2[v]);
  217. 		if(v == p) continue;
  218. 		if(w + d1[v] == val) val = d2[u];
  219. 		val += w;
  220.  
  221. 		// now change root of auxillary to v
  222. 		if(val > d1[v])
  223. 		{
  224. 			d2[v] = d1[v];
  225. 			d1[v] = val;
  226. 		}
  227. 		else if(val > d2[v])
  228. 			d2[v] = val;
  229. 		dfs1(v,u);
  230. 		// change root of auxillary tree back to u
  231. 		d1[v] = tmp.F;
  232. 		d2[v] = tmp.S;
  233. 	}
  234. }
  235.  
  236. int query_nodes[N];
  237. int main()
  238. {
  239. 	fast_io;
  240. 	cin>>n;
  241. 	for(int i=0; i<n-1; i++)
  242. 	{
  243. 		int u,v,w;
  244. 		cin>>u>>v>>w; u--; v--;
  245. 		g[u].PB(MP(v,w));
  246. 		g[v].PB(MP(u,w));
  247. 	}
  248. 	precompute();
  249. 	int q; cin>>q;
  250. 	while(q--)
  251. 	{
  252. 		int ty; cin>>ty;
  253. 		if(ty == 1) // update edge
  254. 		{
  255. 			int u,v; LL w;
  256. 			cin>>u>>v>>w; u--; v--;
  257. 			updateEdge(u,v,w);
  258. 		}
  259. 		else // subset query
  260. 		{
  261. 			int k; cin>>k;
  262. 			for(int i=0; i<k; i++) cin>>Q[i], Q[i]--;
  263. 			for(int i=0; i<k; i++) query_nodes[i] = Q[i];
  264. 			int root = create_tree(k);
  265. 			dfs(root,root);
  266. 			dfs1(root,root);
  267. 			for(int i=0; i<k; i++) cout<<ans[query_nodes[i]]<<" "; cout<<"\n";
  268. 		}
  269. 	}
  270. 	return 0;
  271. }
Runtime error #stdin #stdout 0s 21048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UyhQDX
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!