fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define pii pair<int, int>
  7. #define pb emplace_back
  8. #define all(a) a.begin(), a.end()
  9. #define task "tree"
  10. using namespace std;
  11.  
  12. const int maxn = 15e4 + 4, mod = 998244353, blocksize = 450;
  13. int n, q, deg[maxn], lz[maxn], cnt = 0, id[maxn];
  14. vector<int> adj[maxn], heavy, child[maxn], lst[maxn];
  15.  
  16. int in[maxn], out[maxn], timer = 0, par[maxn], sz[maxn];
  17. void dfseuler(int u, int p) {
  18.   in[u] = ++timer;
  19.   sz[u] = 1;
  20.   for (int v : adj[u]) {
  21.     if (v == p) continue;
  22.     par[v] = u;
  23.     child[u].pb(v);
  24.     dfseuler(v, u);
  25.     lst[u].pb(in[v]);
  26.     sz[u] += sz[v];
  27.   }
  28.  
  29.   out[u] = timer;
  30. }
  31.  
  32. int bit[maxn];
  33. void update(int i, int val) {
  34.   for (; i <= n; i += i & -i) bit[i] += val;
  35. }
  36.  
  37. void update(int l, int r, int val) {
  38.    update(l, val);
  39.    update(r + 1, -val);
  40. }
  41.  
  42. int get(int i) {
  43.   int ans = 0;
  44.   for (; i > 0; i -= i & -i) ans += bit[i];
  45.   return ans;
  46. }
  47.  
  48. inline bool insubtree(int u, int v) {
  49.   return (in[u] <= in[v] && out[v] <= out[u]);
  50. }
  51.  
  52. int pw(int a, int b) {
  53.   int ans = 1, cur = a % mod;
  54.   while (b) {
  55.     if (b & 1) ans = ans * cur % mod;
  56.     cur = cur * cur % mod;
  57.     b >>= 1;
  58.   }
  59.  
  60.   return ans;
  61. }
  62.  
  63. int getchild(int u, int v) {
  64.   int it = upper_bound(lst[u].begin(), lst[u].end(), in[v]) - lst[u].begin() - 1;
  65.   return child[u][it];
  66. }
  67.  
  68. signed main() {
  69.   ios_base::sync_with_stdio(false);
  70.   cin.tie(NULL);
  71.   if (fopen(task ".inp", "r")) {
  72.     freopen(task ".inp", "r", stdin);
  73.     freopen(task ".out", "w", stdout);
  74.   }
  75.  
  76.   cin >> n >> q;
  77.   for (int u, v, i = 1; i < n; i++) {
  78.     cin >> u >> v;
  79.     adj[u].pb(v);
  80.     adj[v].pb(u);
  81.     deg[u]++;
  82.     deg[v]++;
  83.   }
  84.  
  85.   dfseuler(1, -1);
  86.   cnt = 0;
  87.   for (int i = 1; i <= n; i++) {
  88.     if (deg[i] > blocksize) {
  89.       id[i] = ++cnt;
  90.       heavy.pb(i);
  91.     }
  92.   }
  93.  
  94.   while (q--) {
  95.     int t, v;
  96.     cin >> t >> v;
  97.     if (t == 1) {
  98.       int d; cin >> d;
  99.       if (id[v]) lz[v] += d;
  100.       else {
  101.         update(in[v], in[v], n * d);
  102.         for (int son : adj[v]) {
  103.           if (son == par[v]) continue;
  104.           update(in[son], (n - sz[son]) * d);
  105.           update(out[son] + 1, - (n - sz[son]) * d);
  106.         }
  107.  
  108.         update(1, n, sz[v] * d);
  109.         update(in[v], out[v], -sz[v] * d);
  110.       }
  111.     } else {
  112.       int ans = get(in[v]);
  113.       for (int u : heavy) {
  114.         if (u == v) ans += lz[u] * n;
  115.         else if (insubtree(u, v)) ans += lz[u] * (n - sz[getchild(u, v)]);
  116.         else ans += lz[u] * sz[u];
  117.       }
  118.  
  119.       cout << ans % mod * pw(n, mod - 2) % mod << '\n';
  120.     }
  121.   }
  122.  
  123.   return 0;
  124. }
  125.  
  126.  
  127.  
Success #stdin #stdout 0.01s 19988KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Zz4BZr
language:
C++14 (gcc 8.3)
created:
3 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!