fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i,a,b) for(int i=a;i<b;i++)
  4. #define REP(i,b) FOR(i,0,b)
  5. #define PB push_back
  6. #define MP make_pair
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. typedef pair<int,int> pii;
  12.  
  13. int read(){
  14. 	int i;
  15. 	scanf("%d",&i);
  16. 	return i;
  17. }
  18.  
  19. const int maxN=100000;
  20. const int maxQ=100000;
  21. const int B=400;
  22. pii vv[maxN];
  23. vector<int> orgT[maxN];
  24.  
  25. struct Event{
  26. 	int t,a,b,c;
  27. } evs[maxQ];
  28. struct Edge{
  29. 	int to,dist;
  30. };
  31. struct Query{
  32. 	int i,a,b;
  33. };
  34. int ans[maxQ];
  35. struct Range{
  36. 	int l,r,v;
  37. };
  38. struct MyDeque{
  39. 	Range buf[B*4+1];
  40. 	int mx[B*4+1];
  41. 	int b,m,e;
  42. 	void Init(){
  43. 		b=B*2;
  44. 		m=B*2;
  45. 		e=B*2;
  46. 	}
  47. 	void Reset(){
  48. 		m=(b+e)/2;
  49. 		mx[m-1]=buf[m-1].v;
  50. 		for(int i=m-2;i>=b;i--)
  51. 			mx[i]=max(mx[i+1],buf[i].v);
  52. 		mx[m]=buf[m].v;
  53. 		FOR(i,m+1,e)
  54. 			mx[i]=max(mx[i-1],buf[i].v);
  55. 	}
  56. 	int FrontMax(){
  57. 		return b<m?mx[b]:INT_MIN;
  58. 	}
  59. 	void PushFront(Range x){
  60. 		buf[b-1]=x;
  61. 		mx[b-1]=max(x.v,FrontMax());
  62. 		b--;
  63. 	}
  64. 	Range PopFront(){
  65. 		if(b==m){
  66. 			if(e==b+1)
  67. 				return buf[--e];
  68. 			else
  69. 				Reset();
  70. 		}
  71. 		return buf[b++];
  72. 	}
  73. 	int BackMax(){
  74. 		return m<e?mx[e-1]:INT_MIN;
  75. 	}
  76. 	void PushBack(Range x){
  77. 		buf[e]=x;
  78. 		mx[e]=max(x.v,BackMax());
  79. 		e++;
  80. 	}
  81. 	Range PopBack(){
  82. 		if(m==e){
  83. 			if(e==b+1)
  84. 				return buf[b++];
  85. 			else
  86. 				Reset();
  87. 		}
  88. 		return buf[--e];
  89. 	}
  90. 	bool Empty(){
  91. 		return b==e;
  92. 	}
  93. 	int GetMax(){
  94. 		return max(FrontMax(),BackMax());
  95. 	}
  96. } mdq;
  97. int na[B*2],ansRange[B*2][2];
  98. void Sub(const vector<Query>& lq,const vector<Query>& rq,const vector<int>& arr){
  99. 	const int len=arr.size(),qc=lq.size()+rq.size();
  100. 	int li=0,ri=0,al=0,ar=len-1;
  101. 	mdq.Init();
  102. 	mdq.PushBack(Range{0,len-1,INT_MIN});
  103. 	REP(i,qc){
  104. 		Query cur;
  105. 		bool leftQ;
  106. 		if(li==(int)lq.size()){
  107. 			cur=rq[ri++];
  108. 			leftQ=false;
  109. 		}else if(ri==(int)rq.size()){
  110. 			cur=lq[li++];
  111. 			leftQ=true;
  112. 		}else if(lq[li].i<rq[ri].i){
  113. 			cur=lq[li++];
  114. 			leftQ=true;
  115. 		}else{
  116. 			cur=rq[ri++];
  117. 			leftQ=false;
  118. 		}
  119. 		na[i]=-1;
  120. 		if(cur.a!=-1){
  121. 			cur.b=min(cur.b,len-1);
  122. 			if(leftQ){
  123. 				Range w=Range{0,cur.b,cur.a};
  124. 				while(!mdq.Empty()){
  125. 					Range x=mdq.PopFront();
  126. 					if(w.r<x.r){
  127. 						x.l=w.r+1;
  128. 						mdq.PushFront(x);
  129. 						break;
  130. 					}
  131. 				}
  132. 				mdq.PushFront(w);
  133. 				al=max(al,cur.b+1);
  134. 			}else{
  135. 				Range w=Range{len-1-cur.b,len-1,cur.a};
  136. 				while(!mdq.Empty()){
  137. 					Range x=mdq.PopBack();
  138. 					if(x.l<w.l){
  139. 						x.r=w.l-1;
  140. 						mdq.PushBack(x);
  141. 						break;
  142. 					}
  143. 				}
  144. 				mdq.PushBack(w);
  145. 				ar=min(ar,len-1-cur.b-1);
  146. 			}
  147. 		}else if(leftQ){
  148. 			ans[cur.i]=max(ans[cur.i],mdq.GetMax());
  149. 			na[i]=cur.i;
  150. 		}
  151. 		ansRange[i][0]=al;
  152. 		ansRange[i][1]=ar;
  153. 	}
  154. 	int lastL=-1,lastR=-1,mx=INT_MIN;
  155. 	for(int i=qc-1;i>=0;i--)
  156. 		if(na[i]!=-1)
  157. 			if(ansRange[i][0]<=ansRange[i][1]){
  158. 				if(lastL==-1&&lastR==-1){
  159. 					FOR(j,ansRange[i][0],ansRange[i][1]+1)
  160. 						mx=max(mx,arr[j]);
  161. 				}else{
  162. 					FOR(j,ansRange[i][0],lastL)
  163. 						mx=max(mx,arr[j]);
  164. 					FOR(j,lastR+1,ansRange[i][1]+1)
  165. 						mx=max(mx,arr[j]);
  166. 				}
  167. 				lastL=ansRange[i][0];
  168. 				lastR=ansRange[i][1];
  169. 				ans[na[i]]=max(ans[na[i]],mx);
  170. 			}
  171. }
  172.  
  173. bool nowUse[maxN];
  174. vector<int> orgArr[B*4];
  175. vector<Edge> cmpT[B*4];
  176. vector<Query> cmpQ[B*4];
  177. int cmpIdx[maxN],idxInv[B*4],cmpPar[B*4],orgPar[maxN],cmpDep[B*4],raw[B*4];
  178. int MarkDfs(int v,int p,int& idx){
  179. 	orgPar[v]=p;
  180. 	int k=0,ret=0;
  181. 	for(auto&& i:orgT[v])
  182. 		if(i!=p)
  183. 			k+=MarkDfs(i,v,idx);
  184. 	if(k)ret=1;
  185. 	if(k>=2)
  186. 		nowUse[v]=true;
  187. 	if(nowUse[v]){
  188. 		cmpIdx[v]=idx;
  189. 		raw[idx]=vv[v].second;
  190. 		idxInv[idx++]=v;
  191. 		ret=1;
  192. 	}
  193. 	return ret;
  194. }
  195. void SetDepth(int v,int p,int d){
  196. 	cmpDep[v]=d;
  197. 	for(auto&& e:cmpT[v])
  198. 		if(e.to!=p)
  199. 			SetDepth(e.to,v,d+1);
  200. }
  201. void UpdateDfs(int v,int p,int i,int val,int d){
  202. 	if(d<0)
  203. 		return;
  204. 	raw[v]=val;
  205. 	cmpQ[v].PB(Query{i,val,d});
  206. 	for(auto&& e:cmpT[v])
  207. 		if(e.to!=p)
  208. 			UpdateDfs(e.to,v,i,val,d-e.dist);
  209. }
  210. struct DistVal{
  211. 	int d;
  212. 	pii v;
  213. } dvBuf[B];
  214. void ReplaceDfs(int v,int p,int idx,int d){
  215. 	if(nowUse[v]&&p!=-1)
  216. 		return;
  217. 	if(idx>=0&&dvBuf[idx].d<d)
  218. 			idx--;
  219. 	if(idx==-1)
  220. 		return;
  221. 	vv[v]=max(vv[v],dvBuf[idx].v);
  222. 	for(auto&& i:orgT[v])
  223. 		if(i!=p)
  224. 			ReplaceDfs(i,v,idx,d+1);
  225. }
  226. void Solve(int evb,int eve){
  227. 	memset(nowUse,false,sizeof(nowUse));
  228. 	FOR(i,evb,eve)
  229. 		if(evs[i].t==1){
  230. 			nowUse[evs[i].a]=true;
  231. 		}else{
  232. 			nowUse[evs[i].a]=true;
  233. 			nowUse[evs[i].b]=true;
  234. 		}
  235. 	int root=evs[evb].a;
  236. 	int cmpSize=0;
  237. 	MarkDfs(root,-1,cmpSize);
  238. 	root=cmpIdx[root];
  239. 	REP(i,cmpSize){
  240. 		cmpT[i].clear();
  241. 		cmpQ[i].clear();
  242. 	}
  243. 	REP(i,cmpSize)if(i!=root){
  244. 		int v=idxInv[i],x=orgPar[v],d=1;
  245. 		orgArr[i].clear();
  246. 		orgArr[i].PB(vv[v].second);
  247. 		while(!nowUse[x]){
  248. 			orgArr[i].PB(vv[x].second);
  249. 			x=orgPar[x];
  250. 			d++;
  251. 		}
  252. 		orgArr[i].PB(vv[x].second);
  253. 		cmpPar[i]=cmpIdx[x];
  254. 		cmpT[i].PB(Edge{cmpPar[i],d});
  255. 		cmpT[cmpPar[i]].PB(Edge{i,d});
  256. 	}
  257. 	SetDepth(root,-1,0);
  258. 	FOR(i,evb,eve)
  259. 		if(evs[i].t==1)
  260. 			UpdateDfs(cmpIdx[evs[i].a],-1,i,evs[i].c,evs[i].b);
  261. 		else{
  262. 			int x=cmpIdx[evs[i].a],y=cmpIdx[evs[i].b];
  263. 			if(x==y){
  264. 				ans[i]=raw[x];
  265. 			}else{
  266. 				if(cmpDep[x]>cmpDep[y])
  267. 					swap(x,y);
  268. 				while(cmpDep[x]<cmpDep[y]){
  269. 					cmpQ[y].PB(Query{i,-1,evs[i].c});
  270. 					y=cmpPar[y];
  271. 				}
  272. 				while(x!=y){
  273. 					cmpQ[x].PB(Query{i,-1,evs[i].c});
  274. 					x=cmpPar[x];
  275. 					cmpQ[y].PB(Query{i,-1,evs[i].c});
  276. 					y=cmpPar[y];
  277. 				}
  278. 			}
  279. 		}
  280. 	REP(i,cmpSize)if(i!=root)
  281. 		Sub(cmpQ[i],cmpQ[cmpPar[i]],orgArr[i]);
  282. 	REP(i,cmpSize){
  283. 		int k=0;
  284. 		for(auto q:cmpQ[i])
  285. 			if(q.a!=-1){
  286. 				while(k){
  287. 					DistVal dv=dvBuf[k-1];
  288. 					if(dv.d>q.b)
  289. 						break;
  290. 					k--;
  291. 				}
  292. 				dvBuf[k++]=DistVal{q.b,MP(q.i,q.a)};
  293. 			}
  294. 		ReplaceDfs(idxInv[i],-1,k-1,0);
  295. 	}
  296. }
  297.  
  298. int main(){
  299. 	int n=read(),q=read();
  300. 	REP(i,n)
  301. 		vv[i]=MP(-1,read());
  302. 	REP(i,n-1){
  303. 		int a=read()-1,b=read()-1;
  304. 		orgT[a].PB(b);
  305. 		orgT[b].PB(a);
  306. 	}
  307. 	REP(i,q){
  308. 		int t=read(),a=read(),b=read(),c=read();
  309. 		if(t==1)a--;
  310. 		if(t==2)a--,b--,c=i;
  311. 		evs[i]=Event{t,a,b,c};
  312. 		if(i%B==B-1)
  313. 			Solve(i+1-B,i+1);
  314. 	}
  315. 	if(q%B)
  316. 		Solve(q/B*B,q);
  317. 	REP(i,q)
  318. 		if(evs[i].t==2)
  319. 			printf("%d\n",ans[i]);
  320. }
  321.  
Success #stdin #stdout 0s 8376KB
comments (?)
stdin
copy 
5 5
3
2
5
2
6
1 2
2 3
3 5
3 4
2 1 5 0
1 4 1 7
2 5 2 0
1 3 1 2
2 4 1 0
stdout
copy 
6
7
3
https://ideone.com/iOXmbY
language:
C++14 (gcc 8.3)
created:
7 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!