fork download 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-12-07 17:30:08
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-12-07 23:25:04
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define ll long long 
  19. #define ull unsigned long long
  20. #define sz(x) x.size()
  21. #define sqr(x) (1LL * (x) * (x))
  22. #define all(x) x.begin(), x.end()
  23. #define fill(f,x) memset(f,x,sizeof(f))
  24. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  25. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  26. #define debug(x) cout << #x << " = " << x << '\n'
  27. #define ii pair<int,int>
  28. #define iii pair<int,ii>
  29. #define di pair<ii,ii>
  30. #define vi vector<int>
  31. #define vii vector<ii>
  32. #define mii map<int,int>
  33. #define fi first
  34. #define se second
  35. #define pb push_back
  36. #define MOD 1000000007
  37. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  38. #define YES cout << "YES\n"
  39. #define NO cout << "NO\n"
  40. #define MASK(i) (1LL << (i))
  41. #define c_bit(i) __builtin_popcountll(i)
  42. #define BIT(x,i) ((x) & MASK(i))
  43. #define SET_ON(x,i) ((x) | MASK(i))
  44. #define SET_OFF(x,i) ((x) & ~MASK(i))
  45. #define oo 1e18
  46. #define name "TAODULIEU"
  47. #define endl '\n'
  48. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  49. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  50. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  51. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  52. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  53. const int N = (int)3e5+10;
  54. int n;
  55. vi g[N];
  56. ii edge[N];
  57.  
  58. namespace sub14 {
  59.  
  60. 	bool visited[N];
  61.  
  62. 	bool approved() {
  63. 		return n <= 100;
  64. 	}
  65.  
  66. 	void solve(void)
  67. 	{
  68. 		int ans = 0;
  69. 		FOR(L,1,n)
  70. 			FOR(R,L,n)
  71. 			{
  72. 				if (L == 1 and R == n) continue;
  73. 				int len = R-L+1;
  74. 				FOR(i,1,n) visited[i] = false;
  75. 				queue<int> q;
  76. 				q.push(L);
  77. 				visited[L] = true;
  78. 				int cnt = 0;
  79. 				while (!q.empty())
  80. 				{
  81. 					int u = q.front();
  82. 					q.pop();
  83. 					++cnt;
  84. 					for (int v : g[u])
  85. 						if (!visited[v] and v >= L and v <= R)
  86. 						{
  87. 							visited[v] = true;
  88. 							q.push(v);
  89. 						}
  90. 				}
  91. 				ans += (cnt == len);
  92. 			}
  93. 		cout << ans;
  94. 	}
  95.  
  96. }
  97.  
  98. namespace sub25 {
  99.  
  100. 	int par[N],sz[N];
  101.  
  102. 	bool approved() {
  103. 		return n <= 5e3;
  104. 	}
  105.  
  106. 	struct DSU {
  107. 		int n;
  108.  
  109. 		DSU() {};
  110. 		DSU(int _n):
  111. 			n(_n) {};
  112.  
  113. 		void init()
  114. 		{
  115. 			FOR(i,1,n)
  116. 			{
  117. 				par[i] = -1;
  118. 				sz[i] = 0;
  119. 			}
  120. 		} 
  121.  
  122. 		void makeSet(int x)
  123. 		{
  124. 			par[x] = x;
  125. 			sz[x] = 1;
  126. 		}
  127.  
  128. 		int acs(int u) {
  129. 			if (par[u] == -1) return -1;
  130. 			return (u == par[u] ? u : par[u] = acs(par[u]));
  131. 		}
  132.  
  133. 		bool join(int u, int v)
  134. 		{
  135. 			int x = acs(u), y = acs(v);
  136. 			if (x == -1 or y == -1) return false;
  137. 			if (x != y)
  138. 			{
  139. 				if (sz[x] < sz[y]) swap(x,y);
  140. 				sz[x] += sz[y];
  141. 				par[y] = x;
  142. 				return true;
  143. 			}
  144. 			return false;
  145. 		}
  146. 	} dsu;
  147.  
  148. 	void solve(void)
  149. 	{
  150. 		dsu = DSU(n);
  151. 		int ans = 0;
  152. 		FOR(L,1,n)
  153. 		{
  154. 			dsu.init();
  155. 			int tplt = 0;
  156. 			FOR(R,L,n)
  157. 			{
  158. 				dsu.makeSet(R);
  159. 				tplt++;
  160. 				for (int v : g[R])
  161. 					if (v >= L and v <= R-1)
  162. 						tplt -= (dsu.join(R,v));
  163. 				if (tplt == 1)
  164. 					ans += !(L == 1 and R == n);
  165. 			}
  166. 		}
  167. 		cout << ans;
  168. 	}
  169.  
  170. }
  171.  
  172. namespace sub36 {
  173.  
  174. 	vi G[N];
  175.  
  176. 	struct SegmentTree {
  177. 		vi lazy,cnt,mx;
  178. 		int n;
  179.  
  180. 		SegmentTree() {};
  181. 		SegmentTree(int _n):
  182. 			n(_n), lazy((_n<<2)+1,0), cnt((_n<<2)+1,0), mx((_n<<2)+1,0) {};
  183.  
  184. 		void down(int id)
  185. 		{
  186. 			if (!lazy[id]) return;
  187. 			int &k = lazy[id];
  188. 			for (int i : {id<<1,id<<1|1})
  189. 			{
  190. 				mx[i] += k;
  191. 				lazy[i] += k;
  192. 			}
  193. 			k = 0;
  194. 		}
  195.  
  196. 		void build(int id, int l, int r)
  197. 		{
  198. 			if (l == r)
  199. 			{
  200. 				mx[id] = -l;
  201. 				cnt[id] = 1;
  202. 				return;
  203. 			}
  204. 			int mid = (l+r)>>1;
  205. 			build(id<<1,l,mid);
  206. 			build(id<<1|1,mid+1,r);
  207. 			cnt[id] = 0;
  208. 			if (mx[id<<1] >= mx[id<<1|1])
  209. 			{
  210. 				mx[id] = mx[id<<1];
  211. 				cnt[id] += cnt[id<<1];
  212. 			}
  213. 			if (mx[id<<1] <= mx[id<<1|1])
  214. 			{
  215. 				mx[id] = mx[id<<1|1];
  216. 				cnt[id] += cnt[id<<1|1];
  217. 			}
  218. 		}
  219.  
  220. 		void update(int id, int l, int r, int u, int v, int val)
  221. 		{
  222. 			if (l > v or r < u) return;
  223. 			if (l >= u and r <= v)
  224. 			{
  225. 				mx[id] += val;
  226. 				lazy[id] += val;
  227. 				return;
  228. 			}
  229. 			int mid = (l+r)>>1; down(id);
  230. 			update(id<<1,l,mid,u,v,val);
  231. 			update(id<<1|1,mid+1,r,u,v,val);
  232. 			cnt[id] = 0;
  233. 			if (mx[id<<1] >= mx[id<<1|1])
  234. 			{
  235. 				mx[id] = mx[id<<1];
  236. 				cnt[id] += cnt[id<<1];
  237. 			}
  238. 			if (mx[id<<1] <= mx[id<<1|1])
  239. 			{
  240. 				mx[id] = mx[id<<1|1];
  241. 				cnt[id] += cnt[id<<1|1];
  242. 			}
  243. 		}
  244.  
  245. 		int get(int id, int l, int r, int u, int v, int val)
  246. 		{
  247. 			if (l > v or r < u) return 0;
  248. 			if (l >= u and r <= v) return (mx[id] == val ? cnt[id] : 0);
  249. 			int mid = (l+r)>>1; down(id);
  250. 			return get(id<<1,l,mid,u,v,val)+get(id<<1|1,mid+1,r,u,v,val);
  251. 		}
  252. 	} IT;
  253.  
  254. 	void solve(void)
  255. 	{
  256. 		IT = SegmentTree(n);
  257. 		IT.build(1,1,n);
  258. 		int ans = 0;
  259. 		FOR(i,1,n-1) 
  260. 		{
  261. 			auto [u,v] = edge[i];
  262. 			G[min(u,v)].pb(max(u,v));
  263. 			IT.update(1,1,n,max(u,v),n,1);
  264. 		}
  265. 		FOR(L,1,n)
  266. 		{
  267. 			ans += IT.get(1,1,n,L,n,-L);
  268. 			for (int v : G[L])
  269. 				IT.update(1,1,n,v,n,-1);
  270. 		}
  271. 		cout << ans-1;
  272. 	}
  273.  
  274. }
  275.  
  276. bool M2;
  277. signed main()
  278. {
  279.     fast;
  280.     if (fopen(name".inp","r"))
  281.     {
  282.     	freopen(name".inp","r",stdin);
  283.     	freopen(name".out","w",stdout);
  284.     }
  285.     cin >> n;
  286.     FOR(i,1,n-1)
  287.     {
  288.     	int u,v;
  289.     	cin >> u >> v;
  290.     	edge[i] = {u,v};
  291.     	g[u].pb(v); g[v].pb(u);
  292.     }
  293.     if (sub14::approved()) return sub14::solve(), time(), memory(), 0;
  294.     if (sub25::approved()) return sub25::solve(), time(), memory(), 0;
  295.     sub36::solve();
  296.     time();
  297.     memory();
  298.     return 0;
  299. }
  300. // ██░ ██  █    ██  ███▄    █   ▄████
  301. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  302. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  303. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  304. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  305. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  306. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  307. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  308. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 19388KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
-------------Time:8.912ms.
23.1753 MB
https://ideone.com/S2ODy4
language:
C++14 (gcc 8.3)
created:
1 day 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!