fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long n, p, q, ans[200069], dsu[200069], sm[200069], szp, szq;
  5. vector<long long> cc[200069];
  6. const long long mo = 998244353;
  7.  
  8. void mrg(long long x, long long y)
  9. {
  10. 	y = cc[dsu[y]][0];
  11. 	x = cc[dsu[x]][0];
  12. 	while (cc[y].size())
  13. 	{
  14. 		ans[cc[y].back()] = (ans[cc[y].back()]+sm[y]-sm[x]+mo)%mo;
  15. 		dsu[cc[y].back()] = x;
  16. 		cc[x].push_back(cc[y].back());
  17. 		cc[y].pop_back();
  18. 	}
  19. }
  20.  
  21. long long fe(long long x, long long y)
  22. {
  23. 	long long res = 1;
  24. 	while (y)
  25. 	{
  26. 		if (y%2) res = (res*x)%mo;
  27. 		x = (x*x)%mo;
  28. 		y /= 2;
  29. 	}
  30. 	return res;
  31. }
  32.  
  33. int main()
  34. {
  35. 	long long i;
  36. 	scanf("%lld", &n);
  37. 	for (i=1; i<=n; i++)
  38. 	{
  39. 		dsu[i] = i;
  40. 		cc[i].push_back(i);
  41. 	}
  42. 	for (i=1; i<=n-1; i++)
  43. 	{
  44. 		scanf("%lld%lld", &p, &q);
  45. 		szp = cc[dsu[p]].size();
  46. 		szq = cc[dsu[q]].size();
  47. 		printf("p = %lld q = %lld szp = %lld szq = %lld dsu[p] = %lld dsu[q] = %lld\n", p, q, szp, szq, dsu[p], dsu[q]);
  48. 		if (szp<szq) swap(p, q);
  49. 		(sm[dsu[p]] += szp*fe(szp+szq, mo-2)%mo) %= mo;
  50. 		(sm[dsu[q]] += szq*fe(szp+szq, mo-2)%mo) %= mo;
  51. 		mrg(p, q);
  52. 	}
  53. 	for (i=1; i<=n; i++) printf("%lld ", (ans[i]+sm[dsu[i]])%mo);
  54. 	printf("\n");
  55. }
Success #stdin #stdout 0.01s 10860KB
comments (?)
stdin 
5
1 2
4 3
5 3
1 4
stdout 
p = 1 q = 2 szp = 1 szq = 1 dsu[p] = 1 dsu[q] = 2
p = 4 q = 3 szp = 1 szq = 1 dsu[p] = 4 dsu[q] = 3
p = 5 q = 3 szp = 1 szq = 2 dsu[p] = 5 dsu[q] = 4
p = 1 q = 4 szp = 2 szq = 3 dsu[p] = 1 dsu[q] = 4
299473307 299473307 33274813 33274813 865145107
https://ideone.com/Oaauqv
language:
C++ (gcc 8.3)
created:
11 days 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!