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. if (szp<szq)
  48. {
  49. swap(p, q);
  50. swap(szp, szq);
  51. }
  52. (sm[dsu[p]] += szp*fe(szp+szq, mo-2)%mo) %= mo;
  53. (sm[dsu[q]] += szq*fe(szp+szq, mo-2)%mo) %= mo;
  54. mrg(p, q);
  55. }
  56. for (i=1; i<=n; i++) printf("%lld ", (ans[i]+sm[dsu[i]])%mo);
  57. printf("\n");
  58. }
Success #stdin #stdout 0.01s 11980KB
stdin
15
9 2
8 10
13 6
12 11
7 10
4 10
14 2
5 4
1 15
15 2
6 9
8 11
6 3
2 8
stdout
43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290