fork download
copy 
  1. //Tanuj Khattar
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef pair<int,int>   II;
  7. typedef vector< II >      VII;
  8. typedef vector<int>     VI;
  9. typedef vector< VI > 	VVI;
  10. typedef long long int 	LL;
  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. //FILE *fin = freopen("in","r",stdin);
  43. //FILE *fout = freopen("out","w",stdout);
  44.  
  45. const int N = int(1e5)+10;
  46. const int LOGN = 20;
  47. int U[N],V[N],W[N],done[N],Start[LOGN][N],End[LOGN][N],E[N],sub[N],idx[N],level[N],par[N];
  48. vector<LL> BIT[N];
  49. VI g[N];
  50. map<II,int> mp;
  51. int adj(int u,int e)
  52. {
  53. 	return U[e]==u?V[e]:U[e];
  54. }
  55. /************************ BIT **************************/
  56. void update(vector<LL>& BIT,int x,LL add)
  57. {
  58. 	for(;x<SZ(BIT);x+=(x^(x&(x-1))))
  59. 		BIT[x]+=add;
  60. }
  61. LL query(vector<LL>& BIT,int x)
  62. {
  63. 	LL ret=0;
  64. 	for(;x;x=x&(x-1))ret+=BIT[x];
  65. 	return ret;
  66. }
  67. /******************* Centroid Decomposition ********************/
  68. int nn=0;
  69. void dfs0(int u,int ee)
  70. {
  71. 	sub[u]=1;nn++;
  72. 	for(auto e:g[u])
  73. 		if(e!=ee && !done[e])
  74. 		{
  75. 			int w = adj(u,e);
  76. 			dfs0(w,e);
  77. 			sub[u]+=sub[w];
  78. 		}
  79. }
  80. int dfs1(int u,int ee)
  81. {
  82. 	for(auto e:g[u])
  83. 		if(e!=ee && !done[e])
  84. 		{
  85. 			int w = adj(u,e);
  86. 			if(sub[w]>nn/2)
  87. 				return dfs1(w,e);
  88. 		}
  89. 	return u;
  90. }
  91. int lvl,T,cid=-1;
  92. void dfs2(int u,int ee,LL dist=0)
  93. {
  94. 	Start[lvl][u]=++T;
  95. 	update(BIT[cid],T,dist);
  96. 	update(BIT[cid],T+1,-dist);
  97. 	for(auto e:g[u])
  98. 		if(e!=ee && !done[e])
  99. 		{
  100. 			int w = adj(u,e);
  101. 			dfs2(w,e,dist+W[e]);
  102. 		}
  103. 	End[lvl][u]=T;
  104. }
  105. void decompose(int u,int p)
  106. {
  107. 	nn=0;dfs0(u,-1);
  108. 	int root = dfs1(u,-1);
  109. 	par[root]=p;lvl=level[root]=level[p]+1;
  110. 	idx[root]=++cid;BIT[cid] = vector<LL>(nn+2,0);
  111. 	T=0;dfs2(root,-1);
  112. 	for(auto e:g[root]){
  113. 		if(done[e])continue;
  114. 		done[e]=1;E[e]=root;
  115. 		decompose(adj(root,e),root);
  116. 	}
  117. }
  118. /*********************** Handle the queries ***************************/
  119. LL ans[N],dist[LOGN][N],cntbn[N],vis[N];
  120. int Q[N],k,test;
  121. pair<LL,LL> best[N],inf;
  122. void go()
  123. {
  124. 	//clear
  125. 	for(int i=0;i<k;i++){
  126. 		int x = Q[i];
  127. 		while(x)
  128. 			best[x]=inf,cntbn[x]=0,vis[x]=0,x=par[x];
  129. 	}
  130. 	//find cntbn
  131. 	for(int i=0;i<k;i++){
  132. 		int x = Q[i],y=par[x];
  133. 		best[x].F=max(best[x].F,0ll);
  134. 		while(y)
  135. 		{
  136. 			LL d = query(BIT[idx[y]],Start[level[y]][Q[i]]);
  137. 			dist[level[y]][Q[i]]=d;
  138. 			cntbn[x]=max(cntbn[x],d);
  139. 			x = par[x];y=par[y];
  140. 		}
  141. 	}
  142. 	//find best
  143. 	for(int i=0;i<k;i++){
  144. 		int x = Q[i],y=par[x];
  145. 		while(y)
  146. 		{
  147. 			if(!vis[x])
  148. 			{
  149. 				vis[x]=1;
  150. 				LL d = cntbn[x];
  151. 				if(d>best[y].F)best[y].S=best[y].F,best[y].F=d;
  152. 				else if(d>best[y].S)best[y].S=d;
  153. 			}
  154. 			x = par[x],y = par[y];
  155. 		}
  156. 	}
  157. 	//compute the answers
  158. 	for(int i=0;i<k;i++){
  159. 		int x = Q[i],y = par[x];
  160. 		ans[i] = best[x].F;
  161. 		while(y){
  162. 			LL d1 = dist[level[y]][Q[i]];
  163. 			LL d2 = (cntbn[x]==best[y].F?best[y].S:best[y].F);
  164. 			ans[i]=max(ans[i],d1+d2);
  165. 			x = par[x],y = par[y];
  166. 		}
  167. 	}
  168. 	//done :)
  169. }
  170. int main()
  171. {
  172. 	inf={-LL(1e18),-LL(1e18)};
  173. 	int n;si(n);
  174. 	for(int i=1;i<n;i++)
  175. 	{
  176. 		scanf("%d %d %d",U+i,V+i,W+i);
  177. 		g[U[i]].PB(i);
  178. 		g[V[i]].PB(i);
  179. 		mp[MP(min(U[i],V[i]),max(U[i],V[i]))]=i;
  180. 	}
  181. 	decompose(1,0);
  182. 	int q;si(q);
  183. 	while(q--)
  184. 	{
  185. 		test++;
  186. 		int t;si(t);
  187. 		if(t==1)
  188. 		{
  189. 			int u,v;LL w;
  190. 			si(u);si(v);sll(w);
  191. 			if(u>v)swap(u,v);
  192. 			int e = mp[MP(u,v)],x = E[e];
  193. 			while(x){
  194. 				int y = (Start[level[x]][u]>Start[level[x]][v]?u:v);
  195. 				update(BIT[idx[x]],Start[level[x]][y],w - W[e]);
  196. 				update(BIT[idx[x]],End[level[x]][y]+1,W[e] - w);
  197. 				x = par[x];
  198. 			}
  199. 			W[e]=w;
  200. 		}
  201. 		else
  202. 		{
  203. 			si(k);
  204. 			for(int i=0;i<k;i++)si(Q[i]);
  205. 			go();
  206. 			for(int i=0;i<k;i++)printf("%lld ",ans[i]);
  207. 			printf("\n");
  208. 		}
  209. 	}
  210. 	return 0;
  211. }
Runtime error #stdin #stdout 0.06s 45904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2YnsZc
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!