fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using pii = pair<int, int>;
  5.  
  6. vector<vector<pii>> adj(100005);
  7. vector<ll> ran;
  8. ll pref1[100005], pref2[100005], pref3[100005], pref4[100005], pref5[100005], pref6[100005];
  9. ll ogw[100005], val[100005], ans[100005];
  10. int siz[100005], del[100005], nw[100005];
  11. const ll mod = 998244353;
  12. int n;
  13.  
  14. void dfssize(int u, int p){
  15.     siz[u] = 1;
  16.     for (pii e : adj[u]){
  17.         int v = e.second;
  18.         if (v == p || del[v]) continue;
  19.         dfssize(v, u);
  20.         siz[u] += siz[v];
  21.     }
  22. }
  23.  
  24. int dfscentroid(int u, int p, int m){
  25.     for (pii e : adj[u]){
  26.         int v = e.second;
  27.         if (v == p || del[v]) continue;
  28.         if (siz[v]*2 > m) return dfscentroid(v, u, m);
  29.     }
  30.     return u;
  31. }
  32.  
  33. void dfs1(int u, int p){
  34.     for (pii e : adj[u]){
  35.         int i = e.first, v = e.second;
  36.         if (v == p || del[v]) continue;
  37.  
  38.         ran.push_back(ogw[i]);
  39.         dfs1(v, u);
  40.     }
  41. }
  42.  
  43. void dfs2(int u, int p){
  44.     for (pii e : adj[u]){
  45.         int i = e.first, v = e.second;
  46.         if (v == p || del[v]) continue;
  47.  
  48.         int d = distance(ran.begin(), lower_bound(ran.begin(), ran.end(), ogw[i], greater<ll>()))+1;
  49.         nw[i] = d;
  50.         val[d] = ogw[i];
  51.         dfs2(v, u);
  52.     }
  53. }
  54.  
  55. void dfs3(int u, int p, int h, int res){
  56.     pref1[res] = (pref1[res] + h)%mod;
  57.     pref2[res] = (pref2[res] + (ll)h*h)%mod;
  58.     pref3[res] = (pref3[res] + val[res]*h)%mod;
  59.     pref4[res] = (pref4[res] + val[res]*h*h)%mod;
  60.     pref5[res]++;
  61.     pref6[res] = (pref6[res] + val[res])%mod;
  62.  
  63.     for (pii e : adj[u]){
  64.         int i = e.first, v = e.second;
  65.         if (v == p || del[v]) continue;
  66.  
  67.         int nres = res;
  68.         if (val[res] > ogw[i] || !res) nres = nw[i];
  69.         dfs3(v, u, h+1, nres);
  70.     }
  71. }
  72.  
  73. void dfs4(int u, int p, int h, int res, int l){
  74.     ans[u] = (ans[u] + ((val[res]*(pref5[res]-1))%mod*h)%mod*h*l)%mod;
  75.     ans[u] = (ans[u] + ((pref6[ran.size()]-pref6[res])*h)%mod*h*l)%mod;
  76.     if (ans[u] < 0) ans[u] += mod;
  77.  
  78.     for (pii e : adj[u]){
  79.         int i = e.first, v = e.second;
  80.         if (v == p || del[v]) continue;
  81.  
  82.         int nres = res;
  83.         if (val[res] > ogw[i] || !res) nres = nw[i];
  84.         dfs4(v, u, h+1, nres, l);
  85.     }
  86. }
  87.  
  88. void dfs5(int u, int p, int h, int res, int l){
  89.     ans[u] = (ans[u] + (val[res]*pref2[res])%mod*l)%mod;
  90.     ans[u] = (ans[u] + (val[res]*pref1[res])%mod*2*h*l)%mod;
  91.     ans[u] = (ans[u] + (pref4[ran.size()]-pref4[res])*l)%mod;
  92.     ans[u] = (ans[u] + (pref3[ran.size()]-pref3[res])*2*h*l)%mod;
  93.     if (ans[u] < 0) ans[u] += mod;
  94.  
  95.     for (pii e : adj[u]){
  96.         int i = e.first, v = e.second;
  97.         if (v == p || del[v]) continue;
  98.  
  99.         int nres = res;
  100.         if (val[res] > ogw[i] || !res) nres = nw[i];
  101.         dfs5(v, u, h+1, nres, l);
  102.     }
  103. }
  104.  
  105. void decompose(int u){
  106.     dfssize(u, 0);
  107.     int centroid = dfscentroid(u, 0, siz[u]);
  108.  
  109.     dfs1(centroid, 0);
  110.     sort(ran.begin(), ran.end(), greater<ll>());
  111.     ran.erase(unique(ran.begin(), ran.end()), ran.end());
  112.     dfs2(centroid, 0);
  113.     dfs3(centroid, 0, 0, 0);
  114.     for (int i = 1; i <= ran.size(); i++){
  115.         pref1[i] = (pref1[i] + pref1[i-1])%mod;
  116.         pref2[i] = (pref2[i] + pref2[i-1])%mod;
  117.         pref3[i] = (pref3[i] + pref3[i-1])%mod;
  118.         pref4[i] = (pref4[i] + pref4[i-1])%mod;
  119.         pref5[i] = (pref5[i] + pref5[i-1])%mod;
  120.         pref6[i] = (pref6[i] + pref6[i-1])%mod;
  121.     }
  122.     dfs4(centroid, 0, 0, 0, 1);
  123.     dfs5(centroid, 0, 0, 0, 1);
  124.     for (int i = 0; i <= ran.size(); i++){
  125.         pref1[i] = pref2[i] = pref3[i] = pref4[i] = pref5[i] = pref6[i] = 0;
  126.     }
  127.     ran.clear();
  128.  
  129.     dfssize(centroid, 0);
  130.     for (pii e : adj[centroid]){
  131.         int i = e.first, v = e.second;
  132.         if (del[v]) continue;
  133.  
  134.         dfs1(v, centroid);
  135.         ran.push_back(ogw[i]);
  136.         sort(ran.begin(), ran.end(), greater<ll>());
  137.         ran.erase(unique(ran.begin(), ran.end()), ran.end());
  138.         int d = distance(ran.begin(), lower_bound(ran.begin(), ran.end(), ogw[i], greater<ll>()))+1;
  139.         nw[i] = d;
  140.         val[d] = ogw[i];
  141.         dfs2(v, centroid);
  142.         dfs3(v, centroid, 1, nw[i]);
  143.         for (int i = 1; i <= ran.size(); i++){
  144.             pref1[i] = (pref1[i] + pref1[i-1])%mod;
  145.             pref2[i] = (pref2[i] + pref2[i-1])%mod;
  146.             pref3[i] = (pref3[i] + pref3[i-1])%mod;
  147.             pref4[i] = (pref4[i] + pref4[i-1])%mod;
  148.             pref5[i] = (pref5[i] + pref5[i-1])%mod;
  149.             pref6[i] = (pref6[i] + pref6[i-1])%mod;
  150.         }
  151.         dfs4(v, centroid, 1, nw[i], -1);
  152.         dfs5(v, centroid, 1, nw[i], -1);
  153.         for (int i = 0; i <= ran.size(); i++){
  154.             pref1[i] = pref2[i] = pref3[i] = pref4[i] = pref5[i] = pref6[i] = 0;
  155.         }
  156.         ran.clear();
  157.     }
  158.     del[centroid] = 1;
  159.  
  160.     for (pii e : adj[centroid]){
  161.         int v = e.second;
  162.         if (del[v]) continue;
  163.         decompose(v);
  164.     }
  165. }
  166.  
  167. int main(){
  168.     ios::sync_with_stdio(0);
  169.     cin.tie(0);
  170.  
  171.     freopen("netw.inp", "r", stdin);
  172.     freopen("netw.out", "w", stdout);
  173.  
  174.     cin >> n;
  175.     for (int i = 1; i < n; i++){
  176.         int u, v; ll w; cin >> u >> v >> w;
  177.         adj[u].push_back({i, v});
  178.         adj[v].push_back({i, u});
  179.         ogw[i] = w;
  180.     }
  181.     decompose(1);
  182.  
  183.     for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
  184. }
  185.  
Success #stdin #stdout 0.01s 7312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8JAuA4
language:
C++14 (clang 8.0)
created:
1 hour 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!