fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<ll, ll>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. struct Item
  12. {
  13.     int top;
  14.     ll min_dist, dist;
  15.  
  16.     Item(int top = 0, ll min_dist = 0, ll dist = 0) :
  17.         top(top), min_dist(min_dist), dist(dist) {};
  18.     bool operator < (Item other) const
  19.     {
  20.         return min_dist < other.min_dist;
  21.     }
  22. };
  23.  
  24. const int maxn = 1e5;
  25. const int MOD = 998244353;
  26. const ll INF = 1e18;
  27.  
  28. int n, sz[maxn + 10];
  29. ll ans[maxn + 10];
  30. bool del[maxn + 10];
  31. vector<ii> adj[maxn + 10];
  32. vector<Item> c_global, c_internal;
  33.  
  34. void build_sz(int top, int p = -1)
  35. {
  36.     sz[top] = 1;
  37.     for (ii pr : adj[top])
  38.     {
  39.         int next_top = pr.fi;
  40.         if (next_top == p || del[next_top])
  41.             continue;
  42.         build_sz(next_top, top);
  43.         sz[top] += sz[next_top];
  44.     }
  45. }
  46. int find_centroid(int top, int p, int tree_sz)
  47. {
  48.     for (ii pr : adj[top])
  49.     {
  50.         int next_top = pr.fi;
  51.         if (next_top == p || del[next_top])
  52.             continue;
  53.         if (2 * sz[next_top] > tree_sz)
  54.             return find_centroid(next_top, top, tree_sz);
  55.     }
  56.     return top;
  57. }
  58. void travelsel(int top, int p, ll min_dist, int dist)
  59. {
  60.     c_global.push_back(Item(top, min_dist, dist));
  61.     c_internal.push_back(Item(top, min_dist, dist));
  62.  
  63.     for (ii pr : adj[top])
  64.     {
  65.         int next_top = pr.fi;
  66.         ll w = pr.se;
  67.         if (next_top == p || del[next_top])
  68.             continue;
  69.         travelsel(next_top, top, min(min_dist, w), dist + 1);
  70.     }
  71. }
  72. void calc(vector<Item> &it, int sign)
  73. {
  74.     sort(it.begin(), it.end());
  75.     ll sum_dist = 0;
  76.     ll sum_square_dist = 0;
  77.     ll sum_min_dist = 0;
  78.     for (int i = it.size() - 1; i + 1; i--)
  79.     {
  80.         int top = it[i].top;
  81.         ll min_dist = it[i].min_dist;
  82.         ll dist = it[i].dist;
  83.         int cnt = it.size() - i - 1;
  84.         (ans[top] += sign * min_dist * (dist * dist % MOD * cnt + 2 * dist * sum_dist % MOD + sum_square_dist)) %= MOD;
  85.         (sum_dist += dist) %= MOD;
  86.         (sum_square_dist += dist * dist % MOD) %= MOD;
  87.     }
  88.     sum_dist = 0;
  89.     sum_square_dist = 0;
  90.     for (int i = 0; i < it.size(); i++)
  91.     {
  92.         int top = it[i].top;
  93.         ll min_dist = it[i].min_dist;
  94.         ll dist = it[i].dist;
  95.         (ans[top] += sign * (dist * dist % MOD * sum_min_dist % MOD + 2 * dist * sum_dist % MOD + sum_square_dist)) %= MOD;
  96.         (sum_dist += min_dist * dist % MOD) %= MOD;
  97.         (sum_square_dist += min_dist * dist % MOD * dist % MOD) %= MOD;
  98.         (sum_min_dist += min_dist) %= MOD;
  99.     }
  100. }
  101. void centroid_decomposition(int top)
  102. {
  103.     build_sz(top);
  104.     int centroid = find_centroid(top, -1, sz[top]);
  105.     del[centroid] = 1;
  106.  
  107.     c_global.push_back(Item(centroid, INF, 0));
  108.  
  109.     for (ii pr : adj[centroid])
  110.     {
  111.         int next_top = pr.fi;
  112.         ll w = pr.se;
  113.         if (del[next_top])
  114.             continue;
  115.         travelsel(next_top, centroid, w, 1);
  116.         calc(c_internal, -1);
  117.         c_internal.clear();
  118.     }
  119.     calc(c_global, 1);
  120.     c_global.clear();
  121.  
  122.     for (ii pr : adj[centroid])
  123.     {
  124.         int next_top = pr.fi;
  125.         if (del[next_top])
  126.             continue;
  127.         centroid_decomposition(next_top);
  128.     }
  129. }
  130.  
  131. int main()
  132. {
  133.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  134.     if (fopen("NETW.INP", "r"))
  135.     {
  136.         freopen("NETW.INP", "r", stdin);
  137.         freopen("NETW.OUT", "w", stdout);
  138.     }
  139.  
  140.     cin >> n;
  141.     for (int i = 1; i < n; i++)
  142.     {
  143.         int x, y;
  144.         ll w;
  145.         cin >> x >> y >> w;
  146.         adj[x].push_back({y, w});
  147.         adj[y].push_back({x, w});
  148.     }
  149.     centroid_decomposition(1);
  150.     for (int i = 1; i <= n; i++)
  151.         cout << (ans[i] + MOD) % MOD, el;
  152. }
  153.  
Success #stdin #stdout 0.01s 6856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WYNTXE
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!