fork download
copy 
  1. #pragma GCC optimize("-O3","-funroll-all-loops","-ffast-math")
  2. #include <iostream>
  3. #include <stdio.h>
  4. #include <math.h>
  5. #include <string.h>
  6. #include <time.h>
  7. #include <stdlib.h>
  8. #include <string>
  9. #include <bitset>
  10. #include <vector>
  11. #include <set>
  12. #include <map>
  13. #include <queue>
  14. #include <algorithm>
  15. #include <sstream>
  16. #include <stack>
  17. #include <iomanip>
  18. #include <assert.h>
  19. using namespace std;
  20. #define pb push_back
  21. #define mp make_pair
  22. typedef pair<int,int> pii;
  23. typedef long long ll;
  24. typedef double ld;
  25. typedef vector<int> vi;
  26. #define fi first
  27. #define se second
  28. #define fe first
  29. #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
  30. #define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
  31. #define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
  32. #define es(x,e) (int e=fst[x];e;e=nxt[e])
  33. #define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
  34. #define SZ 666666
  35. int T,n,m,ea[SZ],eb[SZ],ec[SZ];
  36. #define M M_ 
  37. int M=0,fst[SZ],vb[SZ],nxt[SZ];
  38. void ad_de(int a,int b)
  39. {++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}
  40. void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
  41. #undef M
  42. char s[SZ];
  43. int sz[SZ],son[SZ],dep[SZ],fa[SZ];
  44. const int M=262144;
  45. int ls[SZ],rs[SZ],ss[SZ];
  46. #define CL(x) memset(x,0,sizeof x)
  47. namespace Seg
  48. {
  49. bool tk[SZ];
  50. int ta[SZ],mi[SZ],mc[SZ];
  51. ll su[SZ],ms[SZ],tb[SZ];
  52. inline void clr()
  53. {
  54. 	CL(mi); CL(su);
  55. 	CL(ms); CL(tb); CL(ta);
  56. 	for(int i=0;i<SZ;++i) tk[i]=1,mi[i]=1e9;
  57. }
  58. inline void pd(int x)
  59. {
  60. 	if(ta[x]||tb[x]||tk[x]!=1);
  61. 	else return;
  62. 	mi[x]+=ta[x]; su[x]-=ms[x];
  63. 	ms[x]=ms[x]*tk[x]+mc[x]*tb[x];
  64. 	su[x]+=ms[x];
  65. 	if(x<=M)
  66. 	{
  67. 		ta[x+x]+=ta[x],ta[x+x+1]+=ta[x];
  68. 		int u=min(mi[x+x],mi[x+x+1]);
  69. 		if(mi[x+x]==u)
  70. 		{
  71. 		tk[x+x]&=tk[x];
  72. 		tb[x+x]=tb[x+x]*tk[x]+tb[x];
  73. 		}
  74. 		if(mi[x+x+1]==u)
  75. 		{
  76. 		tk[x+x+1]&=tk[x];
  77. 		tb[x+x+1]=tb[x+x+1]*tk[x]+tb[x];
  78. 		}
  79. 	}
  80. 	ta[x]=tb[x]=0; tk[x]=1;
  81. }
  82. inline void upd(int x)
  83. {
  84. 	pd(x+x); pd(x+x+1);
  85. 	su[x]=su[x+x]+su[x+x+1];
  86. 	if(mi[x+x]<mi[x+x+1])
  87. 		mi[x]=mi[x+x],mc[x]=mc[x+x],ms[x]=ms[x+x];
  88. 	else if(mi[x+x]>mi[x+x+1])
  89. 		mi[x]=mi[x+x+1],mc[x]=mc[x+x+1],ms[x]=ms[x+x+1];
  90. 	else mi[x]=mi[x+x],
  91. 	mc[x]=mc[x+x]+mc[x+x+1],
  92. 	ms[x]=ms[x+x]+ms[x+x+1];
  93. //	mi[x]=min(mi[x+x],mi[x+x+1]); mc[x]=ms[x]=0;
  94. //	if(mi[x]==mi[x+x]) mc[x]+=mc[x+x],ms[x]+=ms[x+x];
  95. //	if(mi[x]==mi[x+x+1]) mc[x]+=mc[x+x+1],ms[x]+=ms[x+x+1];
  96. }
  97. inline void add(int x,int ql,int qr,int v)
  98. {
  99. 	if(ql>qr||rs[x]<ql||qr<ls[x]) return;
  100. 	pd(x);
  101. 	if(ql<=ls[x]&&rs[x]<=qr)
  102. 	{
  103. 		ta[x]+=v; return;
  104. 	}
  105. 	add(x+x,ql,qr,v);
  106. 	add(x+x+1,ql,qr,v);
  107. 	upd(x);
  108. }
  109. inline int qmin(int x,int ql,int qr)
  110. {
  111. 	if(ql>qr||rs[x]<ql||qr<ls[x]) return 2e9;
  112. 	pd(x);
  113. 	if(ql<=ls[x]&&rs[x]<=qr) return mi[x];
  114. 	int g=min(qmin(x+x,ql,qr),
  115. 	qmin(x+x+1,ql,qr));
  116. 	upd(x); return g;
  117. }
  118. inline ll qsum(int x,int ql,int qr)
  119. {
  120. 	if(ql>qr||rs[x]<ql||qr<ls[x]) return 0;
  121. 	pd(x);
  122. 	if(ql<=ls[x]&&rs[x]<=qr) return su[x];
  123. 	ll g=qsum(x+x,ql,qr)+qsum(x+x+1,ql,qr);
  124. 	upd(x); return g;
  125. }
  126. inline void pt(int x,int ql,int qr,int u,int k,int b)
  127. {
  128. 	if(ql>qr||rs[x]<ql||qr<ls[x]) return;
  129. 	pd(x);
  130. 	if(mi[x]>u) return;
  131. 	if(ql<=ls[x]&&rs[x]<=qr)
  132. 	{
  133. 		assert(mi[x]==u);
  134. //		cerr<<"PUTSHIT:"<<ls[x]<<"~"<<rs[x]<<" "<<k<<","<<b<<"\n";
  135. 		tk[x]=k; tb[x]=b; return;
  136. 	}
  137. 	pt(x+x,ql,qr,u,k,b);
  138. 	pt(x+x+1,ql,qr,u,k,b);
  139. 	upd(x);
  140. }
  141. inline pair<int,ll> qms(int x,int ql,int qr)
  142. {
  143. 	if(ql>qr||rs[x]<ql||qr<ls[x])
  144. 		return pair<int,ll>(2e9,0);
  145. 	pd(x);
  146. 	if(ql<=ls[x]&&rs[x]<=qr)
  147. 		return pair<int,ll>(mi[x],ms[x]);
  148. 	pair<int,ll> g=qms(x+x,ql,qr);
  149. 	pd(x+x+1);
  150. 	if(mi[x+x+1]>g.fi)
  151. 	{
  152. 		upd(x); return g;
  153. 	}
  154. 	pair<int,ll> h=qms(x+x+1,ql,qr);
  155. 	upd(x);
  156. 	if(g.fi<h.fi) return g;
  157. 	if(g.fi>h.fi) return h;
  158. 	return pair<int,ll>(g.fi,g.se+h.se);
  159. }
  160. inline void eds(int x,int p,ll s)
  161. {
  162. 	pd(x);
  163. 	if(ls[x]==rs[x])
  164. 	{
  165. 		su[x]=ms[x]=s;
  166. 		return;
  167. 	}
  168. 	if(p<=rs[x+x])
  169. 		eds(x+x,p,s);
  170. 	else eds(x+x+1,p,s);
  171. 	upd(x);
  172. }
  173. }
  174. void dfs(int x,int f=0)
  175. {
  176. 	sz[x]=1; dep[x]=dep[f]+1; fa[x]=f; son[x]=0;
  177. 	for esb(x,e,b) if(b!=f)
  178. 	{
  179. 		dfs(b,x); sz[x]+=sz[b];
  180. 		if(sz[b]>sz[son[x]]) son[x]=b;
  181. 	}
  182. }
  183. int bs[SZ];
  184. void edt(int x,int y)
  185. {
  186. 	for(;x<SZ;x+=x&-x) bs[x]+=y;
  187. }
  188. int qs(int x)
  189. {
  190. 	int s=0;
  191. 	for(;x>=1;x-=x&-x) s+=bs[x];
  192. 	return s;
  193. }
  194. namespace B2
  195. {
  196. int bs[SZ];
  197. void edt(int x,int y)
  198. {
  199. 	for(;x<SZ;x+=x&-x) bs[x]+=y;
  200. }
  201. int qs(int x)
  202. {
  203. 	int s=0;
  204. 	for(;x>=1;x-=x&-x) s+=bs[x];
  205. 	return s;
  206. }
  207. int qs(int l,int r)
  208. {return qs(r)-qs(l-1);}
  209. }
  210. int top[SZ],fe[SZ],rv[SZ],C,ed[SZ],p1[SZ],p2[SZ],Q=0;
  211. void dfs2(int x,int t)
  212. {
  213. 	top[x]=t; fe[x]=++C; rv[C]=x; p1[x]=++Q;
  214. 	if(son[x]) dfs2(son[x],t);
  215. 	for esb(x,e,b)
  216. 		if(b!=son[x]&&b!=fa[x])
  217. 			dfs2(b,b);
  218. 	ed[x]=C; p2[x]=++Q;
  219. }
  220. int lca(int a,int b)
  221. {
  222. 	while(top[a]!=top[b])
  223. 	{
  224. 		if(dep[top[a]]<dep[top[b]]) b=fa[top[b]];
  225. 		else a=fa[top[a]];
  226. 	}
  227. 	if(dep[a]<dep[b]) return a;
  228. 	return b;
  229. }
  230. int lt[SZ],E=3; ll la[SZ];
  231. #define EDT ++E
  232. namespace Seg2
  233. {
  234. int g[SZ];
  235. void upd(int x,int y)
  236. {
  237. 	x+=M; g[x]=y;
  238. 	while(x>>=1)
  239. 		g[x]=max(g[x+x],g[x+x+1]);
  240. }
  241. int lp(int x,int ql,int qr,int u)
  242. {
  243. 	if(ql>qr||rs[x]<ql||qr<ls[x]||g[x]<u) return 0;
  244. 	if(ls[x]==rs[x]) return ls[x];
  245. 	int uu=lp(x+x+1,ql,qr,u);
  246. 	if(uu) return uu;
  247. 	return lp(x+x,ql,qr,u);
  248. }
  249. }
  250. int ftop(int x)
  251. {return rv[Seg2::lp(1,1,fe[x],ed[x])];}
  252. inline int fc(int x) {return qs(p1[x]);}
  253. set<int> w;
  254. ll ca=0;
  255. ll QS(int x)
  256. {
  257. 	if(lt[x]==E) return la[x];
  258. 	lt[x]=E;
  259. 	return la[x]=Seg::qms(1,fe[x],ed[x]).se;
  260. }
  261. void edb(int x,int v,bool chk=1)
  262. {
  263. 	x=ftop(x);
  264. 	//cerr<<x<<" "<<Seg::qms(1,fe[x],ed[x],F)<<"QWQ\n";
  265. 	int u=fe[x];
  266. 	if(v==-1)
  267. 	{
  268. 		if(!w.count(u)) return;
  269. 		B2::edt(u,-1);
  270. 		if(w.size()<=2)
  271. 		{
  272. 			w.erase(u);
  273. 			ca=0; return;
  274. 		}
  275. 		auto U=w.find(u);
  276. 		int L,R;
  277. 		++U;
  278. 		if(U!=w.end()) R=*U;
  279. 		else R=*w.begin();
  280. 		--U;
  281. 		if(U!=w.begin()) L=*(--U),++U;
  282. 		else L=*w.rbegin();
  283. 		int A=rv[L],B=rv[*U],C=rv[R];
  284. 		int AB=lca(A,B),AC=lca(A,C),BC=lca(B,C);
  285. 		ca-=fc(B)-fc(AB)-fc(BC)+fc(AC);
  286. 		w.erase(U);
  287. 	}
  288. 	else
  289. 	{
  290. 		if(w.count(u)) return;
  291. 		if(chk&&!QS(x)) return;
  292. 		B2::edt(u,1);
  293. 		if(w.size()<=0)
  294. 		{
  295. 			w.insert(u);
  296. 			ca=0; return;
  297. 		}
  298. 		auto U=w.insert(u).fi;
  299. 		int L,R;
  300. 		++U;
  301. 		if(U!=w.end()) R=*U;
  302. 		else R=*w.begin();
  303. 		--U;
  304. 		if(U!=w.begin()) L=*(--U),++U;
  305. 		else L=*w.rbegin();
  306. 		int A=rv[L],B=rv[*U],C=rv[R];
  307. 		int AB=lca(A,B),AC=lca(A,C),BC=lca(B,C);
  308. 		ca+=fc(B)-fc(AB)-fc(BC)+fc(AC);
  309. 	}
  310. }
  311. void flip(int e)
  312. {
  313. 	if(ec[e]) //block
  314. 	{
  315. 		int ww=B2::qs(fe[eb[e]],ed[eb[e]]);
  316. 		if(ww&&ww!=int(w.size())) ca++;
  317. 		edt(p1[eb[e]],1);
  318. 		edt(p2[eb[e]],-1);
  319. 		edb(ea[e],-1);
  320. 		Seg2::upd(fe[eb[e]],ed[eb[e]]);
  321. 		EDT;
  322. 		Seg::add(1,fe[eb[e]],ed[eb[e]],1);
  323. 		ec[e]^=1;
  324. 		edb(ea[e],1);
  325. 		edb(eb[e],1);
  326. 	}
  327. 	else //unblock
  328. 	{
  329. 		int ww=B2::qs(fe[eb[e]],ed[eb[e]]);
  330. 		if(ww&&ww!=int(w.size())) ca--;
  331. 		edt(p1[eb[e]],-1);
  332. 		edt(p2[eb[e]],1);
  333. 		edb(ea[e],-1);
  334. 		edb(eb[e],-1);
  335. 		Seg2::upd(fe[eb[e]],0);
  336. 		EDT;
  337. 		Seg::add(1,fe[eb[e]],ed[eb[e]],-1);
  338. 		ec[e]^=1;
  339. 		edb(ea[e],1);
  340. 	}
  341. }
  342. void sol()
  343. {
  344. 	scanf("%d%d",&n,&m); M_=C=0;
  345. //	cerr<<"+"<<n<<"w"<<m<<"\n";
  346. 	Seg::clr();
  347. 	for(int i=1;i<=n;++i)
  348. 		fst[i]=0,Seg::mc[i+M]=1,Seg::mi[i+M]=0;
  349. 	for(int i=1,a,b;i<n;++i)
  350. 		scanf("%d%d",&a,&b),
  351. 		ea[i]=a,eb[i]=b,ec[i]=0,
  352. 		adde(a,b);
  353. 	dfs(1); dfs2(1,1);
  354. 	for(int i=1;i<=n;++i)
  355. 		Seg2::upd(fe[i],ed[i]);
  356. 	for(int i=1;i<n;++i)
  357. 	{
  358. 		if(fa[ea[i]]==eb[i]) swap(ea[i],eb[i]);
  359. 		assert(fa[eb[i]]==ea[i]);
  360. 	}
  361. 	if(n>1) scanf("%s",s); //is it a trap?
  362. //	for(int i=1;i<=n;++i)
  363. //		cerr<<fe[i]<<",";
  364. //	cerr<<"\n";
  365. 	for(int i=1;i<=n;++i)
  366. 		scanf("%lld",&Seg::su[fe[i]+M]),
  367. 		Seg::ms[fe[i]+M]=Seg::su[fe[i]+M];
  368. 	for(int i=M-1;i>=1;--i)
  369. 		Seg::upd(i);
  370. 	for(int i=1;i<n;++i)
  371. 		Seg::add(1,fe[eb[i]],ed[eb[i]],1),
  372. 		edt(p1[eb[i]],1),
  373. 		edt(p2[eb[i]],-1);
  374. 	for(int i=1;i<=n;++i) edb(i,1);
  375. //	cerr<<ca<<"w"<<ca/2<<" "<<n<<"\n";
  376. //	for(auto p:w)
  377. //		cerr<<rv[p]<<",";cerr<<"\n";
  378. 	for(int i=0;i+1<n;++i)
  379. 		if(s[i]=='0') flip(i+1);
  380. //	cerr<<ca<<"w"<<ca/2<<"\n";
  381. 	while(m--)
  382. 	{
  383. 		int o;
  384. 		scanf("%d",&o);
  385. 		if(o==1)
  386. 		{
  387. 			int e;
  388. 			scanf("%d",&e);
  389. 			flip(e);
  390. 		}
  391. 		else if(o==2)
  392. 		{
  393. 			int x,w;
  394. 			scanf("%d%d",&x,&w);
  395. 			if(w==0) continue;
  396. 			x=ftop(x);
  397. 			int s=fc(x);
  398. 			EDT;
  399. 			Seg::pt(1,fe[x],ed[x],s,1,w);
  400. 			edb(x,1,0);
  401. 		}
  402. 		else if(o==4)
  403. 		{
  404. 			int x;
  405. 			scanf("%d",&x);
  406. 			auto OP=Seg::qsum(1,fe[x],fe[x]);
  407. 			printf("%lld\n",OP);
  408. 			fflush(stdout);
  409. 		}
  410. 		else if(o==5)
  411. 		{
  412. 			int x,x_;
  413. 			scanf("%d",&x);
  414. 			x_=x;
  415. 			x=ftop(x);
  416. //			cerr<<x<<"!\n";
  417. 			int s=fc(x);
  418. 			auto OP=QS(x);
  419. 			printf("%lld\n",OP);
  420. 			fflush(stdout);
  421. 		}
  422. 		else if(o==6)
  423. 		{
  424. 			int x;
  425. 			scanf("%d",&x);
  426. 			x=ftop(x);
  427. 			int s=fc(x); EDT;
  428. 			Seg::pt(1,fe[x],ed[x],s,0,0);
  429. 			edb(x,-1);
  430. 		}
  431. 		else if(o==3)
  432. 		{
  433. 			int x;
  434. 			scanf("%d",&x);
  435. 			int y=ftop(x);
  436. //			cerr<<y<<"!"<<fe[y]<<"w"<<ed[y]<<"\n";
  437. 			int s=fc(y);
  438. 			ll w=QS(y); EDT;
  439. 			Seg::pt(1,fe[y],ed[y],s,0,0);
  440. //			cerr<<"w="<<w<<" y="<<y<<" "<<fe[y]<<"w"<<ed[y]<<"?\n";
  441. //			cerr<<"REP"<<Seg::qms(1,fe[y],fe[y],s)<<" "<<fe[x]<<"?\n";
  442. 			Seg::eds(1,fe[x],w);
  443. 		}
  444. 		else if(o==7)
  445. 		{
  446. 			printf("%lld\n",ca);
  447. //			for(auto u:w)
  448. //				cerr<<u<<",";
  449. //			cerr<<"\n";
  450. 			fflush(stdout);
  451. 		}
  452. 		else throw "???";
  453. 	}
  454. }
  455. int main()
  456. {
  457. 	for(int i=1;i<=M;++i) ls[i+M]=rs[i+M]=i;
  458. 	for(int i=M-1;i>=1;--i)
  459. 		ls[i]=ls[i+i],rs[i]=rs[i+i+1];
  460. 	for(int i=0;i<=M+M;++i)
  461. 		ss[i]=rs[i]-ls[i]+1;
  462. 	scanf("%d",&T); sol();
  463. 	cerr<<clock()<<"ms\n";
  464. }
Success #stdin #stdout #stderr 0s 105152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
11925ms
https://ideone.com/uJzYL7
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!