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. bool alive[MAXN];
  40. int sz[MAXN], dep[MAXN];
  41.  
  42. int mindst[MAXN];
  43. int q[MAXN], qhead, qtail;
  44.  
  45. void dfsinit(int at, int par) {
  46. 	sz[at] = 1, dep[at] = (par == -1 ? 0 : dep[par] + 1);
  47. 	REPSZ(i, adj[at]) {
  48. 		int to = adj[at][i]; if (to == par || !alive[to]) continue;
  49. 		dfsinit(to, at);
  50. 		sz[at] += sz[to];
  51. 	}
  52. }
  53.  
  54. int centroid(int root) {
  55. 	dfsinit(root, -1); int at = root, par = -1;
  56. 	while (true) {
  57. 		bool change = false;
  58. 		REPSZ(i, adj[at]) {
  59. 			int to = adj[at][i]; if (to == par || !alive[to]) continue;
  60. 			if (2 * sz[to] > sz[root]) { change = true; par = at; at = to; break; }
  61. 		}
  62. 		if (!change) return at;
  63. 	}
  64. }
  65.  
  66.  
  67. int cost[MAXN];
  68.  
  69. void modcost(int at, int par, int lim, int by) {
  70. 	int nlim = max(0, min(lim, mindst[at] - dep[at]));
  71. 	FOR(x, nlim, lim) cost[x] += by;
  72. 	REPSZ(i, adj[at]) {
  73. 		int to = adj[at][i]; if (to == par || !alive[to]) continue;
  74. 		modcost(to, at, nlim, by);
  75. 	}
  76. }
  77. void inccost(int at, int lim) {
  78. 	if (dep[at] < lim) ans[at] += cost[dep[at]];
  79. }
  80. void addcost(int at, int par, int lim) {
  81. 	int nlim = min(lim, dep[at] + mindst[at]);
  82. 	inccost(at, nlim);
  83. 	REPSZ(i, adj[at]) {
  84. 		int to = adj[at][i]; if (to == par || !alive[to]) continue;
  85. 		addcost(to, at, nlim);
  86. 	}
  87. }
  88.  
  89. void process(int at) {
  90. 	// Find centroid and initialize tree
  91. 	at = centroid(at);
  92. 	dfsinit(at, -1);
  93. 	// Add costs
  94. 	FOR(x, mindst[at], sz[at]) ++cost[x];
  95. 	REPSZ(i, adj[at]) {
  96. 		int to = adj[at][i]; if (!alive[to]) continue;
  97. 		modcost(to, at, mindst[at], +1);
  98. 	}
  99. 	// Process paths through centroid
  100. 	inccost(at, INT_MAX);
  101. 	REPSZ(i, adj[at]) {
  102. 		int to = adj[at][i]; if (!alive[to]) continue;
  103. 		modcost(to, at, mindst[at], -1);
  104. 		addcost(to, at, INT_MAX);
  105. 		modcost(to, at, mindst[at], +1);
  106. 	}
  107. 	// Remove costs
  108. 	FOR(x, mindst[at], sz[at]) --cost[x];
  109. 	REPSZ(i, adj[at]) {
  110. 		int to = adj[at][i]; if (!alive[to]) continue;
  111. 		modcost(to, at, mindst[at], -1);
  112. 	}
  113. 	// Process paths not going through centroid
  114. 	alive[at] = false;
  115. 	REPSZ(i, adj[at]) {
  116. 		int to = adj[at][i]; if (!alive[to]) continue;
  117. 		process(to);
  118. 	}
  119. }
  120.  
  121. void run() {
  122. 	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); }
  123.  
  124. 	REP(i, n) mindst[i] = INT_MAX; qhead = qtail = 0;
  125. 	REP(i, n) if (SZ(adj[i]) <= 1) mindst[i] = 0, q[qhead++] = i;
  126. 	while (qtail < qhead) {
  127. 		int at = q[qtail++];
  128. 		REPSZ(i, adj[at]){
  129. 			int to = adj[at][i]; if (mindst[to] != INT_MAX) continue;
  130. 			mindst[to] = mindst[at] + 1; q[qhead++] = to;
  131. 		}
  132. 	}
  133.  
  134. 	REP(i, n) alive[i] = true, ans[i] = 0; memset(cost, 0, sizeof(cost));
  135. 	process(0);
  136. 	REP(i, n) printf("%d\n", ans[i]);
  137. }
  138.  
  139. int main() {
  140. 	freopen("atlarge.in", "r", stdin);
  141. 	freopen("atlarge.out", "w", stdout);
  142. 	run();
  143. 	return 0;
  144. }
Success #stdin #stdout 0s 19416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ESSFZB
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!