fork download
copy 
  1. /* Creation Date - 30-01-2023 */  
  2. /* Creation Time - 21:47:56.65 */  
  3. #define ill 
  4. /*
  5. Written By : mafailure
  6. In the name of God 
  7. O Allah, May you grant peace and honor on Muhammad and his family.
  8. Allahumm-a-Sall-iAla Muhammad-in Wa Al-i Muhammad
  9. */
  10.  
  11. #ifdef LOCAL 
  12. #define AATIF_DEBUG
  13. #endif 
  14. /*Add -DLOCAL in 
  15. compiler command 
  16. to trigger it*/
  17.  
  18. #include<bits/stdc++.h>
  19. #include <ext/pb_ds/assoc_container.hpp> // Common file 
  20. #include <ext/pb_ds/tree_policy.hpp> 
  21. #include <functional> // for less
  22. using namespace std;
  23. using namespace __gnu_pbds;
  24. #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  25.  
  26. #define endl "\n"
  27. /*------------------------int to long long -----------------*/
  28. #ifdef ill
  29. #define int long long 
  30. #endif
  31. /*---------------------------DEBUG HELPER--------------------------------------*/
  32. template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
  33. template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
  34. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  35. template<typename T,typename K> ostream& operator<<(ostream & os,const map<T,K> & mapp){ os<<"{"; string sep=""; for(const auto& x:mapp)os<<sep<<x,sep=", "; return os<<'}'; }
  36. template <typename T> ostream & operator<<(ostream & os,const set<T> & sett){os<<'{'; string sep=""; for(const auto & x:sett)os<<sep<<x,sep=", "; return os<<'}';}
  37.  
  38. void dbg_out() { cerr << endl; }
  39. template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
  40.  
  41. #ifdef AATIF_DEBUG
  42. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  43. #else
  44. #define dbg(...)
  45. #endif
  46.  
  47. //#define int long long 
  48. // int dx[]={-1,1,0,0}; int dy[]={0,0,1,-1};
  49. // int dx[]={2,2,-2,-2,1,1,-1,-1}; int dy[]={1,-1,1,-1,2,-2,2,-2};
  50. #ifndef mod_2 
  51. long long mod = 1e9 + 7;
  52. #else 
  53. long long mod =998244353; 
  54. #endif 
  55. const double eps=1e-9;
  56. typedef vector<int> vi;
  57. typedef vector<vi> vvi;
  58. typedef vector<string> vs;
  59. typedef vector<bool> vb;
  60. typedef pair<int, int> ii;
  61. typedef vector< pair< int, int > > vii;
  62. typedef map<int, int> mii;
  63. typedef pair<int, ii> pip;
  64. typedef pair<ii, int> ppi;
  65. #define arrinp(arr,init,final,size,type) type* arr=new type[size];for(int i=init;i<final;i++)cin>>arr[i];
  66. #define cr2d(arr,n,m,t) t**arr=new t*[n];for(int i=0;i<n;i++)arr[i]=new t[m];
  67. #define w(t) int t;cin>>t; while(t--)
  68. #define takeInp(n) int n;cin>>n;
  69. #define fr(i,init,final) for(int i=init;i<final;i++)
  70. #define frr(i,init,final) for(int i=init;i>=final;i--)
  71. #define Fr(i,final) for(int i=0;i<final;i++)
  72. #define Frr(i,first) for(int i=first;i>=0;i--)
  73. #define fi first
  74. #define se second
  75. #define mp make_pair
  76. #define pb push_back
  77. #define all(c) (c).begin(),(c).end()
  78. #define rall(c) (c).rbegin(),(c).rend()
  79. #define debug(x) cerr<<">value ("<<#x<<") : "<<x<<endl;
  80. #define setb __builtin_popcount
  81. #define lsone(n) (n&(-n))
  82. #define rlsone(n) (n&(n-1))
  83. #define clr(a,b) memset(a,b,sizeof(a))
  84. #ifdef ill 
  85. const int inf =1e18; 
  86. #else 
  87. const int inf=1e9;
  88. #endif
  89. /*-----------------------------RANDOM NUMBER GENERATOR ---------------------*/
  90. #ifdef RNG 
  91. unsigned seed=chrono::high_resolution_clock::now().time_since_epoch().count();
  92. mt19937 rng(seed);
  93. #endif 
  94. /*------------------------------UNORDERED MAP HASH --------------------------------------------*/
  95. //To make unordered_map unhackable 
  96. // use it as unordered_map<int,int,custom_hash> mapp;
  97. struct custom_hash {
  98.     static uint64_t splitmix64(uint64_t x) {
  99.         /* http://x...content-available-to-author-only...i.it/splitmix64.c */
  100.         x += 0x9e3779b97f4a7c15;
  101.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  102.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  103.         return x ^ (x >> 31);
  104.     }
  105.  
  106.     size_t operator()(uint64_t x) const {
  107.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  108.         return splitmix64(x + FIXED_RANDOM);
  109.     }
  110. };
  111. /*---------------------------ORDERED SET--------------------------------------*/
  112. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>  ordered_set; 
  113. /*----------------------------------------------------------------------------*/
  114. vi init(string s)
  115. {
  116. 	istringstream sin(s);
  117. 	int n;
  118. 	vi arr;
  119. 	while(sin>>n)arr.push_back(n);
  120. 	return arr;
  121. }
  122. int power(int x, int y)
  123. { 
  124. 	if(y==0)return 1;
  125. 	int u=power(x,y/2);
  126. 	u=(u*u)%mod;
  127. 	if(y%2)u=(x*u)%mod;
  128. 	return u;
  129.  
  130. }
  131. int gcd(int a,int b)
  132. {
  133. 	if(a<b)return gcd(b,a);
  134. 	return (b==0?a:(a%b?gcd(b,a%b):b));
  135. }
  136. int gcd_e(int a,int b,int &x,int &y)
  137. {
  138.  
  139. 	if(b==0){x=1; y=0; return a;}
  140. 	int x1,y1;
  141. 	int p=gcd_e(b,a%b,x1,y1);
  142. 	x=y1;
  143. 	y=x1-(a/b)*y1;
  144. 	return p;
  145. }
  146. /*-----------------to solve int to long long problem-----------------*/
  147. int Min (int a,int b){return min(a,b);}
  148. int Max(int a,int b){ return max(a,b);}
  149. inline int add(int a,int b,int mod=mod){return (a+b)%mod;} 
  150. inline int sub(int a,int b,int mod=mod){return (a-b+mod)%mod;}
  151. inline int mul(int a,int b,int mod=mod){return (a*b%mod);}
  152. inline int divide(int a,int b,int mod=mod){return a*power(b,mod-2)%mod;}
  153. inline int high(int a,int b){return (a>>b)&1;}
  154. //786 121 786 121 786 121 786 121 786 121 786 121 786 121 786 121 786 121
  155. /*========================CODE*****CODE****CODE======================*/
  156.  
  157.  
  158. using namespace std;
  159.  
  160. template <class T = int, class L = int, class A = int>
  161. class segTree
  162. {
  163. public:
  164. #define left (p << 1)
  165. #define right (left | 1)
  166. #define mid ((l + r) >> 1)
  167. #define toleft left, l, mid
  168. #define toright right, mid + 1, r
  169. 	int n;
  170. 	vector<T> t;
  171. 	vector<L> lazy;
  172. 	vector<A> a;
  173. 	// T tmp;
  174. 	segTree(int n) : n(n), t(4 * n), lazy(4 * n,-1) {}
  175. 	T mer(T a, T b){
  176. 	    T c; 
  177. 	    fr(i,0,4)c[i]=a[i]+b[i]; 
  178. 	    return c; 
  179. 		 }
  180. 	void build(int p, int l, int r)
  181. 	{
  182. 		if (l == r)
  183. 		{
  184. 			t[p] = T({0,a[l],0,1});
  185. 			return void();
  186. 		}
  187. 		build(toleft);
  188. 		build(toright);
  189. 		t[p] = mer(t[left], t[right]);
  190. 	}
  191. 	void push(int p, int l, int r)
  192. 	{
  193. 		if(lazy[p]==-1)return; 
  194. 		if(lazy[p]){
  195. 		t[p][1]=t[p][0]+t[p][1];
  196. 		t[p][0]=0;  
  197. 		t[p][3]+=t[p][2]; 
  198. 		t[p][2]=0;
  199. 			}
  200. 		else 
  201. 		{
  202. 			t[p][0]=t[p][0]+t[p][1]; 
  203. 			t[p][1]=0;
  204. 			t[p][2]+=t[p][3];
  205. 			t[p][3]=0;  
  206. 		}
  207. 		if(l!=r)lazy[left]=lazy[right]=lazy[p]; 
  208. 		lazy[p]=-1; 
  209. 		return;
  210. 	}
  211. 	T query(int p, int l, int r, int i, int j)
  212. 	{
  213. 		push(p, l, r);
  214. 		if (i <= l && r <= j)
  215. 			return t[p];
  216. 		if (j <= mid)
  217. 			return query(toleft, i, j);
  218. 		if (i > mid)
  219. 			return query(toright, i, j);
  220. 		return mer(query(toleft, i, j), query(toright, i, j));
  221. 	}
  222. 	template <typename V, typename... Args>
  223. 	void lazy_oper(int p, int l, int r, V val, Args... args)
  224. 	{
  225. 		lazy[p]=val;  
  226. 	}
  227. 	template <typename... V>
  228. 	void update(int p, int l, int r, int i, int j, V... val)
  229. 	{
  230. 		push(p, l, r);
  231. 		if (r < i || l > j)
  232. 			return void();
  233. 		if (i <= l && r <= j)
  234. 		{
  235. 			lazy_oper(p, l, r, val...);
  236. 			push(p, l, r);
  237. 			return;
  238. 		}
  239. 		update(toleft, i, j, val...);
  240. 		update(toright, i, j, val...);
  241. 		t[p] = mer(t[left], t[right]);
  242. 	}
  243.  
  244. #undef toright
  245. #undef toleft
  246. #undef mid
  247. #undef right
  248. #undef left
  249. };
  250.  
  251. template <class T = int, class L = int, class A = int>
  252. class HLD
  253. {
  254. public:
  255. 	segTree<T, L, A> seg;
  256. #define Seg seg
  257. #undef w
  258. 	vvi g;
  259. 	vi depth, par, heavy, node, pos, head, w,endpos,mxpos;
  260.  
  261.  
  262. 	int n, cur_pos; 
  263. 	HLD(int n) : n(n), g(n),endpos(n),mxpos(n), cur_pos(0), depth(n), par(n), w(n), heavy(n, -1), node(n), pos(n), head(n), seg(n) {}
  264. 	void dfs(int u, int p)
  265. 	{
  266. 		w[u] = 1;
  267. 		heavy[u] = -1;
  268. 		int size = 0;
  269. 		par[u] = p;
  270. 		//tin[u]=entry++; 
  271. 		//tout[u]=entry++; 
  272. 		//up[u][0]=p; 
  273. 		//fr(i,1,20)up[u][i]=up[up[u][i-1]][i-1]; 
  274. 		// if(g[u].size()==1)leaf[u]=1;
  275. 		// else leaf[u]=0;
  276. 		for (auto v : g[u])
  277. 		{
  278. 			if (v == p)
  279. 				continue;
  280. 			depth[v] = depth[u] + 1;
  281. 			dfs(v, u);
  282. 			// leaf[u]+=leaf[v];
  283. 			w[u] += w[v];
  284. 			if (w[v] > size)
  285. 				size = w[v], heavy[u] = v;
  286. 		}
  287. 	}
  288.  
  289. 	void decompose(int u, int h)
  290. 	{
  291. 		head[u] = h;
  292. 		pos[u] = cur_pos++;
  293. 		node[pos[u]] = u;  
  294. 		endpos[h]=pos[u]; 
  295. 		mxpos[u]=pos[u]; 
  296. 		if (~heavy[u])
  297. 			decompose(heavy[u], h);
  298. 		for (auto v : g[u])
  299. 		{
  300. 			if (v == par[u] || v == heavy[u])
  301. 				continue;
  302. 			decompose(v, v);
  303. 		}
  304. 		for(auto v:g[u])
  305. 		{
  306. 			if(v==par[u])continue; 
  307. 			mxpos[u]=max(mxpos[u],mxpos[v]); 
  308. 		}
  309. 	}
  310. 	T mer(T a, T b)
  311. 	{
  312. 		T c; 
  313. 		fr(i,0,4)c[i]=a[i]+b[i]; 
  314. 		return c;
  315. 	}
  316.  
  317. 	template <typename V>
  318. 	void update(int u, int v, V val)
  319. 	{
  320. 		for (; head[u] != head[v]; v = par[head[v]])
  321. 		{
  322. 			if (depth[head[u]] > depth[head[v]])
  323. 				swap(u, v);
  324. 			seg.update(1, 0, n - 1, pos[head[v]], pos[v], val);
  325. 		}
  326. 		if (depth[u] > depth[v])
  327. 			swap(u, v);
  328. 		seg.update(1, 0, n - 1, pos[u], pos[v], val);
  329. 	}
  330. 	T query(int u, int v, T ans)
  331. 	{
  332. 		for (; head[u] != head[v]; v = par[head[v]])
  333. 		{
  334. 			if (depth[head[u]] > depth[head[v]])
  335. 				swap(u, v);
  336. 			// dbg(head[v],v);
  337. 			ans = mer(ans, seg.query(1, 0, n - 1, pos[head[v]], pos[v]));
  338. 		}
  339. 		// dbg(u,v);
  340. 		if (depth[u] > depth[v])
  341. 			swap(u, v);
  342.  
  343. 		return ans = mer(ans, seg.query(1, 0, n - 1, pos[u], pos[v]));
  344. 	}
  345. 	void solve();
  346. };
  347.  
  348. template<class T,class L,class A> 
  349. void HLD<T,L,A>:: solve()
  350. {
  351. 	int q; 
  352. 	cin>>q; 
  353. 	fr(i,0,n-1)
  354. 	{
  355. 		int u,v; 
  356. 		cin>>u>>v; 
  357. 		u--; v--; 
  358. 		g[u].pb(v); 
  359. 		g[v].pb(u); 
  360. 	}
  361. 	vi a(n); 
  362. 	fr(i,0,n)cin>>a[i]; 
  363.  
  364.  
  365. 	dfs(0,0); 
  366. 	decompose(0,0);
  367. 	seg.a.resize(n); 
  368. 	fr(i,0,n)seg.a[pos[i]]=a[i]; 
  369. 	seg.build(1,0,n-1); 
  370. 	//segTree sub(n); 
  371.  
  372. 	const int d=20; 
  373. 	/*auto isancestor=[&](int u,int v)->bool 
  374. 	{
  375. 		return tin[u]<=tin[v]&&tout[u]>=tout[v]; 
  376. 	};
  377. 	auto glca=[&](int u,int v)
  378. 	{
  379. 		if(isancestor(u,v))return u; 
  380. 		if(isancestor(v,u))return v; 
  381. 		frr(i,d-1,0)
  382. 		{
  383. 			if(!isancestor(up[u][i],v))u=up[u][i]; 	
  384. 		}
  385. 		return up[u][0]; 
  386. 	};*/
  387.  
  388. 	fr(i,0,q)
  389. 	{
  390. 		int type; 
  391. 		cin>>type; 
  392. 		if(type==1)
  393. 		{
  394. 			int u,v; 
  395. 			cin>>u>>v; 
  396. 			u--; v--; 
  397. 			//int lca=glca(u,v); 
  398. 			T gcnt=query(u,v,T({0,0,0,0})); 
  399. 			if(gcnt[2]==gcnt[3])continue; 
  400. 			if(gcnt[3]>gcnt[2])
  401. 			{
  402. 				update(u,v,1); 
  403. 			}
  404. 			else update(u,v,0); 
  405.  
  406. 		}
  407. 		else if(type==2)
  408. 		{
  409. 			int x; 
  410. 			cin>>x; 
  411. 			x--; 
  412. 			int u=x; 
  413. 			seg.update(1,0,n-1,pos[u],mxpos[u],0); 
  414. 		}
  415. 		else
  416. 		{
  417. 			int x,y;
  418. 			cin>>x>>y;
  419. 			x--; y--; 
  420. 			T gcnt=query(x,y,T({0,0,0,0})); 
  421. 			cout<<max(gcnt[0],gcnt[1])<<endl; 
  422. 		}
  423. 	}
  424.  
  425.  
  426.  
  427.  
  428.  
  429.  
  430. }
  431.  
  432. signed main()
  433. {
  434. 	IOS
  435.  
  436. 	int n; 
  437. 	cin>>n; 
  438. 	HLD<array<int,4>,int,int> hld(n);
  439. 	hld.solve(); 
  440.  
  441.  
  442.  
  443.  
  444. }
  445.  
  446.  
  447.  
  448.  
Runtime error #stdin #stdout 0.01s 5440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/C1aWKM
language:
C++14 (gcc 8.3)
created:
1 year 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!