fork download
copy 
  1. #include <algorithm>  
  2. #include <iostream>  
  3. #include <sstream>  
  4. #include <string>  
  5. #include <cstring>
  6. #include <vector>  
  7. #include <queue>  
  8. #include <set>  
  9. #include <map>  
  10. #include <cstdio>  
  11. #include <cstdlib>  
  12. #include <cctype>  
  13. #include <cmath>  
  14. #include <list>  
  15. #include <cassert>
  16. #include <ctime>
  17. #include <climits>
  18. using namespace std;
  19.  
  20. #define PB push_back  
  21. #define MP make_pair  
  22. #define SZ(v) ((int)(v).size())  
  23. #define FOR(i,a,b) for(int i=(a);i<(b);++i)  
  24. #define REP(i,n) FOR(i,0,n)  
  25. #define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
  26. #define REPE(i,n) FORE(i,0,n)  
  27. #define FORSZ(i,a,v) FOR(i,a,SZ(v))  
  28. #define REPSZ(i,v) REP(i,SZ(v))  
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); }
  32.  
  33. const int MAXN = 70000;
  34.  
  35. int n;
  36. vector<int> adj[MAXN];
  37. int ans[MAXN];
  38.  
  39. int sz[MAXN], heavy[MAXN], dep[MAXN];
  40.  
  41. int mindst[MAXN];
  42. int q[MAXN], qhead, qtail;
  43.  
  44. void dfsinit(int at, int par) {
  45. 	sz[at] = 1, dep[at] = (par == -1 ? 0 : dep[par] + 1), heavy[at] = -1;
  46. 	REPSZ(i, adj[at]) {
  47. 		int to = adj[at][i]; if (to == par) continue;
  48. 		dfsinit(to, at);
  49. 		sz[at] += sz[to]; if (heavy[at] == -1 || sz[to] > sz[heavy[at]]) heavy[at] = to;
  50. 	}
  51. }
  52.  
  53. int acost[MAXN];
  54. void modacost(int at, int par, int deplca, int lim, int by) {
  55. 	int nlim = max(deplca, min(lim, mindst[at] + 2 * deplca - dep[at]));
  56. 	FOR(x, nlim, lim) acost[x] += by;
  57. 	REPSZ(i, adj[at]) {
  58. 		int to = adj[at][i]; if (to == par) continue;
  59. 		modacost(to, at, deplca, nlim, by);
  60. 	}
  61. }
  62.  
  63. int bcost[2 * MAXN + 1], blim;
  64. void modbcost(int at, int par, int lim, int by) {
  65. 	int nlim = mindst[at] - dep[at];
  66. 	FOR(x, nlim, lim) bcost[x + MAXN] += by;
  67. 	REPSZ(i, adj[at]) {
  68. 		int to = adj[at][i]; if (to == par) continue;
  69. 		modbcost(to, at, nlim, by);
  70. 	}
  71. }
  72. void incbcost(int at, int deplca) {
  73. 	ans[at] += dep[at] - 2 * deplca >= blim ? 0 : bcost[dep[at] - 2 * deplca + MAXN]; // >=blim already included in acost
  74. }
  75. void addbcost(int at, int par,int deplca) {
  76. 	incbcost(at, deplca);
  77. 	REPSZ(i, adj[at]) {
  78. 		int to = adj[at][i]; if (to == par) continue;
  79. 		addbcost(to, at, deplca);
  80. 	}
  81. }
  82.  
  83. // Before acost contains all light siblings of ancestors and bcost is empty. Afterwards acost is unchanged and bcost contains the entire subtree.
  84. void process(int at, int par, int alim) {
  85. 	int nalim = dep[at] + mindst[at]; assert(nalim >= alim); FOR(x, alim, nalim) acost[x] = 1; alim = nalim;
  86. 	// for each light subtree: add it to acost
  87. 	REPSZ(i, adj[at]) {
  88. 		int to = adj[at][i]; if (to == par || to == heavy[at]) continue;
  89. 		modacost(to, at, dep[at], alim, +1);
  90. 	}
  91. 	// for each light subtree: remove it from acost, process it, re-add it to acost and remove it from bcost
  92. 	ans[at] += dep[at] >= alim ? 1 : acost[dep[at]];
  93. 	REPSZ(i, adj[at]) {
  94. 		int to = adj[at][i]; if (to == par || to == heavy[at]) continue;
  95. 		modacost(to, at, dep[at], alim, -1);
  96. 		process(to, at, alim);
  97. 		modbcost(to, at, blim, -1);
  98. 		modacost(to, at, dep[at], alim, +1);
  99. 	}
  100. 	// process heavy subtree
  101. 	int nblim = mindst[at] - dep[at];
  102. 	if (heavy[at] != -1) {
  103. 		process(heavy[at], at, alim);
  104. 		assert(nblim >= blim); FOR(x, blim, nblim) bcost[x + MAXN] = 1; blim = nblim;
  105. 	} else {
  106. 		blim = nblim;
  107. 	}
  108. 	// for each light subtree: update answer with bcost
  109. 	incbcost(at, dep[at]);
  110. 	REPSZ(i, adj[at]) {
  111. 		int to = adj[at][i]; if (to == par || to == heavy[at]) continue;
  112. 		addbcost(to, at, dep[at]);
  113. 	}
  114. 	// for each light subtree: remove it from acost and re-add it to bcost
  115. 	REPSZ(i, adj[at]) {
  116. 		int to = adj[at][i]; if (to == par || to == heavy[at]) continue;
  117. 		modacost(to, at, dep[at], alim, -1);
  118. 		modbcost(to, at, blim, +1);
  119. 	}
  120. }
  121.  
  122. void run() {
  123. 	scanf("%d", &n); REP(i, n - 1) { int a, b; scanf("%d%d", &a, &b); --a, --b; adj[a].PB(b); adj[b].PB(a); }
  124.  
  125. 	REP(i, n) mindst[i] = INT_MAX; qhead = qtail = 0;
  126. 	REP(i, n) if (SZ(adj[i]) <= 1) mindst[i] = 0, q[qhead++] = i;
  127. 	while (qtail < qhead) {
  128. 		int at = q[qtail++];
  129. 		REPSZ(i, adj[at]){
  130. 			int to = adj[at][i]; if (mindst[to] != INT_MAX) continue;
  131. 			mindst[to] = mindst[at] + 1; q[qhead++] = to;
  132. 		}
  133. 	}
  134.  
  135. 	REP(i, n) ans[i] = 0; memset(acost, 0, sizeof(acost)); memset(bcost, 0, sizeof(bcost));
  136. 	dfsinit(0, -1);
  137. 	process(0, -1, dep[0] + mindst[0]);
  138. 	REP(i, n) printf("%d\n", ans[i]);
  139. }
  140.  
  141. int main() {
  142. 	//freopen("atlarge.in", "r", stdin);
  143. 	//freopen("atlarge.out", "w", stdout);
  144. 	run();
  145. 	return 0;
  146. }
Success #stdin #stdout 0s 19344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PwvQI4
language:
C++14 (gcc 8.3)
created:
6 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!