fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(1e5)+7;
  14. const int mod = 998244353;
  15.  
  16. int add(int x , int y){
  17.     x += y;
  18.     if (x >= mod) x -= mod;
  19.     return x;
  20. }
  21.  
  22. void self_add(int &x , int y){
  23.     x = add(x , y);
  24. }
  25.  
  26. int sub(int x , int y){
  27.     x -= y;
  28.     if (x < 0) x += mod;
  29.     return x;
  30. }
  31.  
  32. void self_sub(int &x , int y){
  33.     x = sub(x , y);
  34. }
  35.  
  36. int mul(int x , int y){
  37.     return (1ll * x * y) % mod;
  38. }
  39.  
  40. int sqr(int x){
  41.     return mul(x , x);
  42. }
  43.  
  44. int Pow(int a , int n){
  45.     int ans = 1;
  46.     for (; n > 0 ; n /= 2 , a = mul(a , a)){
  47.         if (n&1) ans = mul(ans , a);
  48.     }
  49.     return ans;
  50. }
  51.  
  52. int n;
  53. vector<ii> g[maxN];
  54. int sz[maxN];
  55. bool del[maxN];
  56.  
  57. void dfs_size(int u , int par){
  58.     sz[u] = 1;
  59.     for (ii e : g[u]){
  60.         int v = e.fi;
  61.         if (v != par && del[v] == 0){
  62.             dfs_size(v , u);
  63.             sz[u] += sz[v];
  64.         }
  65.     }
  66. }
  67.  
  68. int dfs_find(int u , int par , int half){
  69.     for (ii e : g[u]){
  70.         int v = e.fi;
  71.         if (v != par && del[v] == 0 && sz[v] > half){
  72.             return dfs_find(v , u , half);
  73.         }
  74.     }
  75.     return u;
  76. }
  77.  
  78. vector<pair<ii , int>> p;
  79.  
  80. void dfs_prepare(int u , int par , int c , int d){
  81.     if (par != 0){
  82.         p.push_back({{c , d} , u});
  83.     }
  84.     for (ii e : g[u]){
  85.         int v = e.fi;
  86.         int w = e.se;
  87.         if (v != par && del[v] == 0){
  88.             dfs_prepare(v , u , min(c , w) , d + 1);
  89.         }
  90.     }
  91. }
  92.  
  93. int f[3] , res[maxN];
  94.  
  95. void prepare(int u , int par , int c , int d){
  96.     dfs_prepare(u , par , c , d);
  97.     if (par == 0){
  98.         for (auto it : p){
  99.             int v = it.se;
  100.             int C = it.fi.fi;
  101.             int D = it.fi.se;
  102.             self_add(res[u] , mul(C , sqr(D)));
  103.             self_add(res[v] , mul(C , sqr(D)));
  104.         }
  105.     }
  106.     sort(all(p));
  107.     f[0] = f[1] = f[2] = 0;
  108.     for (auto it : p){
  109.         int v = it.se;
  110.         int C = it.fi.fi;
  111.         int D = it.fi.se;
  112.         if (par == 0){
  113.             self_add(res[v] , mul(f[0] , sqr(D)));
  114.             self_add(res[v] , mul(f[1] , D));
  115.             self_add(res[v] , f[2]);
  116.         }
  117.         else{
  118.             self_sub(res[v] , mul(f[0] , sqr(D)));
  119.             self_sub(res[v] , mul(f[1] , D));
  120.             self_sub(res[v] , f[2]);
  121.         }
  122.         self_add(f[0] , C);
  123.         self_add(f[1] , mul(2 , mul(C , D)));
  124.         self_add(f[2] , mul(C , sqr(D)));
  125.     }
  126.     reverse(all(p));
  127.     f[0] = f[1] = f[2] = 0;
  128.     for (auto it : p){
  129.         int v = it.se;
  130.         int C = it.fi.fi;
  131.         int D = it.fi.se;
  132.         if (par == 0){
  133.             self_add(res[v] , mul(f[0] , mul(C , sqr(D))));
  134.             self_add(res[v] , mul(f[1] , mul(C , D)));
  135.             self_add(res[v] , mul(f[2] , C));
  136.         }
  137.         else{
  138.             self_sub(res[v] , mul(f[0] , mul(C , sqr(D))));
  139.             self_sub(res[v] , mul(f[1] , mul(C , D)));
  140.             self_sub(res[v] , mul(f[2] , C));
  141.         }
  142.         self_add(f[0] , 1);
  143.         self_add(f[1] , mul(2 , D));
  144.         self_add(f[2] , sqr(D));
  145.     }
  146.     p.clear();
  147. }
  148.  
  149. void dfs_solve(int u){
  150.     dfs_size(u , 0);
  151.     u = dfs_find(u , 0 , sz[u] / 2);
  152.     del[u] = 1;
  153.     prepare(u , 0 , INT_MAX , 0);
  154.     for (ii e : g[u]){
  155.         int v = e.fi;
  156.         int w = e.se;
  157.         if (del[v] == 0) prepare(v , u , w , 1);
  158.     }
  159.     for (ii e : g[u]){
  160.         int v = e.fi;
  161.         if (del[v] == 0){
  162.             dfs_solve(v);
  163.         }
  164.     }
  165. }
  166.  
  167. void solve(){
  168.     cin >> n;
  169.     for (int i = 1 ; i < n ; i++){
  170.         int u , v , w;
  171.         cin >> u >> v >> w;
  172.         g[u].push_back({v , w});
  173.         g[v].push_back({u , w});
  174.     }
  175.     dfs_solve(1);
  176.     for (int i = 1 ; i <= n ; i++) cout << res[i] << "\n";
  177. }
  178.  
  179. #define name "netw"
  180.  
  181. int main(){
  182.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  183.     if (fopen(name".INP" , "r")){
  184.         freopen(name".INP" , "r" , stdin);
  185.         freopen(name".OUT" , "w" , stdout);
  186.     }
  187.     int t = 1; //cin >> t;
  188.     while (t--) solve();
  189.     return 0;
  190. }
  191.  
Success #stdin #stdout 0.01s 5888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/LBf4Fb
language:
C++ (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!