fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <math.h>
  4. #include <string.h>
  5. #include <time.h>
  6. #include <stdlib.h>
  7. #include <string>
  8. #include <bitset>
  9. #include <vector>
  10. #include <set>
  11. #include <map>
  12. #include <queue>
  13. #include <algorithm>
  14. #include <sstream>
  15. #include <stack>
  16. #include <iomanip>
  17. #include <assert.h>
  18. using namespace std;
  19. #define pb push_back
  20. #define mp make_pair
  21. typedef pair<int,int> pii;
  22. typedef long long ll;
  23. typedef double ld;
  24. typedef vector<int> vi;
  25. #define fi first
  26. #define se second
  27. #define fe first
  28. #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
  29. #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);}
  30. #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);}
  31. #define es(x,e) (int e=fst[x];e;e=nxt[e])
  32. #define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
  33. #define SZ 277777
  34. int T,n;
  35. int MM=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];
  36. void ad_de(int a,int b,int c)
  37. {++MM;nxt[MM]=fst[a];fst[a]=MM;vb[MM]=b;vc[MM]=c;}
  38. void adde(int a,int b,int c)
  39. {ad_de(a,b,c);ad_de(b,a,c);}
  40. int M;
  41. int fp[SZ],fc[SZ],top[SZ],dep[SZ],sz[SZ],son[SZ],fa[SZ],C=0;
  42. void dfs(int x,int f=0)
  43. {
  44. 	fa[x]=f; dep[x]=dep[f]+1; son[x]=0; sz[x]=1;
  45. 	for esb(x,e,b) if(b!=f)
  46. 	{
  47. 		fc[b]=vc[e]; dfs(b,x); sz[x]+=sz[b];
  48. 		if(sz[b]>sz[son[x]]) son[x]=b;
  49. 	}
  50. }
  51. int rp[SZ];
  52. void dfs2(int x,int t)
  53. {
  54. 	fp[x]=++C; rp[C]=x; top[x]=t;
  55. 	if(son[x]) dfs2(son[x],t);
  56. 	for esb(x,e,b)
  57. 		if(b!=fa[x]&&b!=son[x])
  58. 			dfs2(b,b);
  59. }
  60. int ls[SZ],rs[SZ],ss[SZ];
  61. namespace Seg
  62. {
  63. bool t1[SZ],t2[SZ];
  64. int su[SZ][2][2],v[SZ][2][2];
  65. void clr()
  66. {
  67. 	for(int i=0;i<=M+M;++i)
  68. 		t1[i]=t2[i]=0,
  69. 		memset(v[i],0,sizeof v[0]),
  70. 		memset(su[i],0,sizeof su[0]);
  71. }
  72. inline void upd(int x)
  73. {
  74. 	if(x<=M)
  75. 	{
  76. 		#define par(a,b) \
  77. 		su[x][a^t1[x]][b^t2[x]]=su[x+x][a][b]+su[x+x+1][a][b];
  78. 		par(0,0) par(0,1) par(1,0) par(1,1);
  79. 		#undef par
  80. 	}
  81. 	else
  82. 	{
  83. 		#define par(a,b) \
  84. 		su[x][a^t1[x]][b^t2[x]]=v[x][a][b];
  85. 		par(0,0) par(0,1) par(1,0) par(1,1);
  86. 		#undef par
  87. 	}
  88. }
  89. void flip(int x,int l,int r,int a,int b)
  90. {
  91. 	if(rs[x]<l||r<ls[x]) return;
  92. 	if(l<=ls[x]&&rs[x]<=r)
  93. 	{
  94. 		t1[x]^=a; t2[x]^=b;
  95. 		upd(x); return;
  96. 	}
  97. 	flip(x+x,l,r,a,b);
  98. 	flip(x+x+1,l,r,a,b);
  99. 	upd(x);
  100. }
  101. }
  102. vector<pii> fj(int a,int b)
  103. {
  104. 	vector<pii> v;
  105. 	while(top[a]!=top[b])
  106. 	{
  107. 		if(dep[top[a]]>dep[top[b]]) swap(a,b);
  108. 		v.pb(pii(fp[top[b]],fp[b])); b=fa[top[b]];
  109. 	}
  110. 	if(dep[a]>dep[b]) swap(a,b);
  111. 	if(a!=b) v.pb(pii(fp[a]+1,fp[b]));
  112. 	return v;
  113. }
  114. int sw[SZ][2],Fc[SZ];
  115. void updn(int x)
  116. {
  117. 	int v[2][2];
  118. 	memset(v,0,sizeof v);
  119. 	if(son[x])
  120. 	{
  121. 	if(x!=1)
  122. 	{
  123. 	for(int a=0;a<2;++a)
  124. 		for(int b=0;b<2;++b)
  125. 			v[a^Fc[x]][b^Fc[son[x]]]=(a!=b)?1:(sw[x][!a]!=0);
  126. 	}
  127. 	else
  128. 	{
  129. 	for(int a=0;a<2;++a)
  130. 		for(int b=0;b<2;++b)
  131. 			v[a^Fc[x]][b^Fc[son[x]]]=1+(sw[x][!b]!=0);
  132. 	}
  133. 	}
  134. //	cout<<"UPDN"<<x<<"!\n";
  135. //	for(int j=0;j<2;++j) for(int k=0;k<2;++k) cout<<v[j][k]<<" ";cout<<"\n";
  136. 	int w=fp[x]+M;
  137. 	memcpy(Seg::v[w],v,sizeof v);
  138. 	while(w) Seg::upd(w),w>>=1;
  139. }
  140. namespace FF{
  141. char ch,B[1<<20],*S=B,*T=B;
  142. #define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)
  143. #define isd(c) (c>='0'&&c<='9')
  144. int aa,bb;int F(){
  145.     while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
  146.     while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return bb?aa:-aa;
  147. }
  148. }
  149. #define gi FF::F()
  150. #define BUFSIZE 5000000
  151. namespace fob {char b[BUFSIZE]={},*f=b,*g=b+BUFSIZE-2;}
  152. #define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
  153. #define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
  154. struct foce {~foce() {pob; fflush(stdout);}} _foce;
  155. namespace ib {char b[100];}
  156. inline void pint(int x)
  157. {
  158.     if(x==0) {pc(48); return;}
  159.     char *s=ib::b;
  160.     while(x) *(++s)=x%10, x/=10;
  161.     while(s!=ib::b) pc((*(s--))+48);
  162. }
  163. void sol()
  164. {
  165. 	n=gi; MM=C=0;
  166. 	for(int i=1;i<=n;++i) fst[i]=sw[i][0]=sw[i][1]=0;
  167. 	M=1; while(M<n+2) M<<=1;
  168. 	for(int i=0;i<=M-1;++i) ls[i+M]=rs[i+M]=i,ss[i]=1;
  169. 	for(int i=M-1;i>=1;--i)
  170. 		ls[i]=ls[i+i],rs[i]=rs[i+i+1],
  171. 		ss[i]=rs[i]-ls[i]+1;
  172. 	for(int i=1,a,b,c;i<n;++i)
  173. 		a=gi,b=gi,c=gi,adde(a,b,c);
  174. 	dfs(1); dfs2(1,1);
  175. 	for(int i=0;i<=n;++i) Fc[i]=fc[i];
  176. 	Seg::clr();
  177. 	for(int i=2;i<=n;++i)
  178. 		if(i!=son[fa[i]]) sw[fa[i]][fc[i]]++;
  179. 	for(int i=1;i<=n;++i) updn(i);
  180. 	int q=gi;
  181. 	while(q--)
  182. 	{
  183. 		int a=gi,b=gi;
  184. 		auto w=fj(a,b);
  185. 		for(auto t_:w)
  186. 		{
  187. 			auto t=t_;
  188. 			//flip range t
  189. 			int u=rp[t.fi];
  190. 			Seg::flip(1,t.fi,t.se,1,0);
  191. 			if(u!=son[fa[u]])
  192. 			{
  193. 				--sw[fa[u]][fc[u]];
  194. 				++sw[fa[u]][fc[u]^=1];
  195. 				updn(fa[u]);
  196. 			}
  197. 			else --t.fi; --t.se;
  198. 			if(t.fi<=t.se) Seg::flip(1,t.fi,t.se,0,1);
  199. 		}
  200. 		pint(Seg::su[1][0][0]); pc(10);
  201. 	}
  202. }
  203. int main()
  204. {
  205. 	T=gi;
  206. 	for(int i=1;i<=T;++i) sol();
  207. }
Time limit exceeded #stdin #stdout 5s 49904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wYL5jL
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!