fork download
copy 
  1. #include<stdio.h>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5. #define SIZE 131072
  6. vector<int>pat[100000];
  7. vector<int>ko[100000];
  8. int par[19][100000];
  9. int depth[100000];
  10. bool flag[100000];
  11. int heavy[100000];
  12. int toseg[100000];
  13. int pattop[100000];
  14. void dfs(int node,int d)
  15. {
  16. 	if(flag[node])
  17. 	{
  18. 		return;
  19. 	}
  20. 	flag[node]=true;
  21. 	depth[node]=d;
  22. 	for(int i=0;i<pat[node].size();i++)
  23. 	{
  24. 		if(!flag[pat[node][i]])
  25. 		{
  26. 			dfs(pat[node][i],d+1);
  27. 			ko[node].push_back(pat[node][i]);
  28. 			par[0][pat[node][i]]=node;
  29. 		}
  30. 	}
  31. }
  32. int num;
  33. void lcainit()
  34. {
  35. 	for(int i=1;i<=18;i++)
  36. 	{
  37. 		for(int j=0;j<num;j++)
  38. 		{
  39. 			par[i][j]=par[i-1][par[i-1][j]];
  40. 		}
  41. 	}
  42. }
  43. int lca(int a,int b)
  44. {
  45. 	if(a==-1)
  46. 	{
  47. 		return b;
  48. 	}
  49. 	if(b==-1)
  50. 	{
  51. 		return a;
  52. 	}
  53. 	if(depth[a]>depth[b])
  54. 	{
  55. 		swap(a,b);
  56. 	}
  57. 	for(int i=18;i>=0;i--)
  58. 	{
  59. 		if(depth[a]+(1<<i)<=depth[b])
  60. 		{
  61. 			b=par[i][b];
  62. 		}
  63. 	}
  64. 	if(a==b)
  65. 	{
  66. 		return a;
  67. 	}
  68. 	for(int i=18;i>=0;i--)
  69. 	{
  70. 		if(par[i][a]!=par[i][b])
  71. 		{
  72. 			a=par[i][a];
  73. 			b=par[i][b];
  74. 		}
  75. 	}
  76. 	return par[0][a];
  77. }
  78. int decomposit(int node)
  79. {
  80. 	int maxi=0,rr;
  81. 	if(ko[node].empty())
  82. 	{
  83. 		heavy[node]=-1;
  84. 		return 1;
  85. 	}
  86. 	int siz=0;
  87. 	for(int i=0;i<ko[node].size();i++)
  88. 	{
  89. 		int z=decomposit(ko[node][i]);
  90. 		if(maxi<z)
  91. 		{
  92. 			maxi=z;
  93. 			rr=ko[node][i];
  94. 			siz+=z;
  95. 		}
  96. 	}
  97. 	heavy[node]=rr;
  98. 	return siz+1;
  99. }
  100. class lcatree
  101. {
  102. public:
  103. 	int seg[SIZE*2];
  104. 	void init()
  105. 	{
  106. 		for(int i=0;i<num;i++)
  107. 		{
  108. 			seg[SIZE+i]=i;
  109. 		}
  110. 		for(int i=num;i<SIZE;i++)
  111. 		{
  112. 			seg[SIZE+i]=-1;
  113. 		}
  114. 		for(int i=SIZE-1;i>=1;i--)
  115. 		{
  116. 			seg[i]=lca(seg[i*2],seg[i*2+1]);
  117. 		}
  118. 	}
  119. 	int getlca(int beg,int end,int node,int lb,int ub)
  120. 	{
  121. 		if(ub<beg||end<lb)
  122. 		{
  123. 			return -1;
  124. 		}
  125. 		if(beg<=lb&&ub<=end)
  126. 		{
  127. 			return seg[node];
  128. 		}
  129. 		return lca(getlca(beg,end,node*2,lb,(lb+ub)/2),getlca(beg,end,node*2+1,(lb+ub)/2+1,ub));
  130. 	}
  131. };
  132. class segtree
  133. {
  134. public:
  135. 	int segmin[SIZE*2];
  136. 	int segnum[SIZE*2];
  137. 	int flag[SIZE*2];
  138. 	void init()
  139. 	{
  140. 		for(int i=0;i<SIZE;i++)
  141. 		{
  142. 			segnum[SIZE+i]=1;
  143. 		}
  144. 		for(int i=SIZE-1;i>=1;i--)
  145. 		{
  146. 			segnum[i]=segnum[i*2]+segnum[i*2+1];
  147. 		}
  148. 	}
  149. 	void update(int beg,int end,int node,int lb,int ub,int num)
  150. 	{
  151. 		if(ub<beg||end<lb)
  152. 		{
  153. 			return;
  154. 		}
  155. 		if(beg<=lb&&ub<=end)
  156. 		{
  157. 			segmin[node]+=num;
  158. 			flag[node]+=num;
  159. 			return;
  160. 		}
  161. 		if(flag[node])
  162. 		{
  163. 			segmin[node*2]+=flag[node];
  164. 			segmin[node*2+1]+=flag[node];
  165. 			flag[node*2]+=flag[node];
  166. 			flag[node*2+1]+=flag[node];
  167. 			flag[node]=0;
  168. 		}
  169. 		update(beg,end,node*2,lb,(lb+ub)/2,num);
  170. 		update(beg,end,node*2+1,(lb+ub)/2+1,ub,num);
  171. 		segnum[node]=0;
  172. 		segmin[node]=min(segmin[node*2],segmin[node*2+1]);
  173. 		if(segmin[node*2]<=segmin[node*2+1])
  174. 		{
  175. 			segnum[node]+=segnum[node*2];
  176. 		}
  177. 		if(segmin[node*2]>=segmin[node*2+1])
  178. 		{
  179. 			segnum[node]+=segnum[node*2+1];
  180. 		}
  181. 	}
  182. 	int get()
  183. 	{
  184. 		if(segmin[1]!=0)
  185. 		{
  186. 			return SIZE;
  187. 		}
  188. 		return SIZE-segnum[1];
  189. 	}
  190. };
  191. lcatree ltree;
  192. segtree tree;
  193. int main()
  194. {
  195. 	int gen;
  196. 	scanf("%d%d",&num,&gen);
  197. 	for(int i=0;i<num-1;i++)
  198. 	{
  199. 		int za,zb;
  200. 		scanf("%d%d",&za,&zb);
  201. 		za--;
  202. 		zb--;
  203. 		pat[za].push_back(zb);
  204. 		pat[zb].push_back(za);
  205. 	}
  206. 	fill(flag,flag+num,false);
  207. 	for(int i=0;i<=18;i++)
  208. 	{
  209. 		for(int j=0;j<num;j++)
  210. 		{
  211. 			par[i][j]=-1;
  212. 		}
  213. 	}
  214. 	dfs(0,0);
  215. 	lcainit();
  216. 	fill(heavy,heavy+num,-1);
  217. 	decomposit(0);
  218. 	int pt=0;
  219. 	for(int i=0;i<num;i++)
  220. 	{
  221. 		if(par[0][i]!=-1)
  222. 		{
  223. 			if(heavy[par[0][i]]==i)
  224. 			{
  225. 				continue;
  226. 			}
  227. 		}
  228. 		int now=i;
  229. 		for(;;)
  230. 		{
  231. 			toseg[now]=pt++;
  232. 			pattop[now]=i;
  233. 			now=heavy[now];
  234. 			if(now==-1)
  235. 			{
  236. 				break;
  237. 			}
  238. 		}
  239. 	}
  240. 	pt=0;
  241. 	ltree.init();
  242. 	tree.init();
  243. 	int maxi=0;
  244. 	for(int i=0;i<num;i++)
  245. 	{
  246. 		int now=i;
  247. 		for(;;)
  248. 		{
  249. 			if(now==-1)
  250. 			{
  251. 				break;
  252. 			}
  253. 			tree.update(toseg[pattop[now]],toseg[now],1,0,SIZE-1,1);
  254. 			now=par[0][pattop[now]];
  255. 		}
  256. 		for(;;)
  257. 		{
  258. 			int l=ltree.getlca(pt,i,1,0,SIZE-1);
  259. 			if(tree.get()-depth[l]>gen)
  260. 			{
  261. 				int n=pt;
  262. 				for(;;)
  263. 				{
  264. 					if(n==-1)
  265. 					{
  266. 						break;
  267. 					}
  268. 					tree.update(toseg[pattop[n]],toseg[n],1,0,SIZE-1,-1);
  269. 					n=par[0][pattop[n]];
  270. 				}
  271. 				pt++;
  272. 			}
  273. 			else
  274. 			{
  275. 				maxi=max(maxi,i-pt+1);
  276. 				break;
  277. 			}
  278. 			if(pt>i)
  279. 			{
  280. 				break;
  281. 			}
  282. 		}
  283. 	}
  284. 	printf("%d\n",maxi);
  285. }
Success #stdin #stdout 0s 18880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/XfJPsS
language:
C++ (gcc 8.3)
created:
10 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!