fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define eprintf(args...) fprintf(stderr, args)
  4. #define rep(i, n) for (int i = 0; i < (int)(n); ++ i)
  5.  
  6. using i64 = long long;
  7.  
  8. const int mxn = 2e5 + 5, mxlg = 20;
  9.  
  10. int n, q, ini[mxn];
  11. std::vector <int> oadj[mxn];
  12. int odfn[mxn], oed[mxn], otim;
  13. std::vector <std::pair <int, std::pair <int, int> > > edges;
  14.  
  15. void dfs2(int u, int p) {
  16.     odfn[u] = ++ otim;
  17.     for (int v : oadj[u]) {
  18.         if (v == p) continue;
  19.         dfs2(v, u);
  20.     }
  21.     oed[u] = otim;
  22. }
  23.  
  24. struct UnionFind {
  25.     int fa[mxn];
  26.     void init() { rep(i, mxn) fa[i] = i; }
  27.     inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
  28.     inline void merge(int x, int y) { fa[find(x)] = find(y); }
  29. } uf;
  30.  
  31. int fa[mxn], jmp[mxn][mxlg], jmp_min[mxn][mxlg];
  32. std::vector <int> adj[mxn];
  33. int wei[mxn];
  34. int root;
  35.  
  36. int dep[mxn], sz[mxn], son[mxn], top[mxn], dfn[mxn], ed[mxn], tim;
  37.  
  38. struct Query {
  39.     int tp, id;
  40.     int x, y, v;
  41.     int pos;
  42. };
  43.  
  44. bool operator < (const Query &a, const Query &b) {
  45.     return a.x != b.x ? a.x < b.x : a.tp > b.tp;
  46. }
  47.  
  48. bool is_qry[mxn];
  49. std::vector <Query> vqry;
  50.  
  51. void dfs0(int u) {
  52.     sz[u] = 1;
  53.     son[u] = -1;
  54.     for (int v : adj[u]) {
  55.         dep[v] = dep[u] + 1;
  56.         dfs0(v);
  57.         sz[u] += sz[v];
  58.         son[u] = !~son[u] || sz[v] > sz[son[u]] ? v : son[u];
  59.     }
  60. }
  61.  
  62. void dfs1(int u) {
  63.     top[u] = u == root || u != son[fa[u]] ? u : top[fa[u]];
  64.     dfn[u] = ++ tim;
  65.     if (~son[u]) dfs1(son[u]);
  66.     for (int v : adj[u]) if (v != son[u]) dfs1(v);
  67.     ed[u] = tim;
  68. }
  69.  
  70. struct BIT {
  71.     i64 s[mxn];
  72.     void update(int x, i64 v) { for (; x < mxn; x += x & -x) s[x] += v; }
  73.     i64 query(int x) { i64 ans = 0; for (; x; x -= x & -x) ans += s[x]; return ans; }
  74. } bit;
  75.  
  76. i64 ans[mxn];
  77.  
  78. void conq(int l, int r) {
  79.     if (l + 1 >= r) return ;
  80.     int mid = (l + r) >> 1;
  81.     conq(l, mid);
  82.     conq(mid, r);
  83.     std::inplace_merge(vqry.begin() + l, vqry.begin() + mid, vqry.begin() + r);
  84.     for (int i = l; i < r; ++ i) {
  85.         Query Q = vqry[i];
  86.         if (Q.tp == 1 && Q.pos < mid) bit.update(Q.y, Q.v);
  87.         if (Q.tp == 0 && Q.pos >= mid) ans[Q.id] += bit.query(Q.y) * Q.v;
  88.     }
  89.     for (int i = l; i < r; ++ i) {
  90.         Query Q = vqry[i];
  91.         if (Q.tp == 1 && Q.pos < mid) bit.update(Q.y, -Q.v);
  92.     }
  93. }
  94.  
  95. int main() {
  96.     // freopen("in", "r", stdin);
  97.     scanf("%d %d", &n, &q);
  98.     rep(i, n) scanf("%d", &ini[i]);
  99.     rep(i, n - 1) {
  100.         int u, v, w;
  101.         scanf("%d %d %d", &u, &v, &w);
  102.         -- u, -- v;
  103.         edges.push_back({w, {u, v}});
  104.         oadj[u].push_back(v);
  105.         oadj[v].push_back(u);
  106.     }
  107.     dfs2(0, -1);
  108.     std::sort(edges.rbegin(), edges.rend());
  109.     uf.init();
  110.     rep(i, n) wei[i] = 0x3f3f3f3f;
  111.     for (auto tr : edges) {
  112.         int w = tr.first;
  113.         int u = tr.second.first;
  114.         int v = tr.second.second;
  115.         u = uf.find(u), v = uf.find(v);
  116.         int x = n ++;
  117.         wei[x] = w;
  118.         adj[x].push_back(u);
  119.         adj[x].push_back(v);
  120.         fa[u] = fa[v] = x;
  121.         uf.merge(u, x);
  122.         uf.merge(v, x);
  123.     }
  124.     root = n - 1;
  125.     fa[root] = root;
  126.     rep(i, n) jmp[i][0] = fa[i], jmp_min[i][0] = std::min(wei[i], wei[fa[i]]);
  127.     rep(j, mxlg - 1) rep(i, n) jmp[i][j + 1] = jmp[jmp[i][j]][j], jmp_min[i][j + 1] = std::min(jmp_min[i][j], jmp_min[jmp[i][j]][j]);
  128.     dfs0(root);
  129.     dfs1(root);
  130.     for(int i = 0; i < n; i++){
  131.     	std::cout << i << ' ' << odfn[i] << ' ' << oed[i] << ' ' << dfn[i] << ' ' << ed[i] << '\n';
  132.     }
  133.     rep(tc, q) {
  134.         int tp; scanf("%d", &tp);
  135.         if (tp == 1) {
  136.             is_qry[tc] = true;
  137.             int u;
  138.             scanf("%d", &u);
  139.             -- u;
  140.             ans[tc] += ini[u];
  141.             vqry.push_back({0, tc, dfn[u], odfn[u], +1});
  142.         } else {
  143.             int x, y, u;
  144.             scanf("%d %d %d", &x, &y, &u);
  145.             -- u;
  146.             int ou = u;
  147.             for (int i = mxlg - 1; ~i; -- i) {
  148.                 if (jmp_min[u][i] >= y) {
  149.                     u = jmp[u][i];
  150.                 }
  151.             }
  152.             std::cout << ou << ' ' << u << '\n';
  153.             vqry.push_back({1, tc, dfn[u], odfn[ou], +x});
  154.             vqry.push_back({1, tc, dfn[u], oed[ou] + 1, -x});
  155.             vqry.push_back({1, tc, ed[u] + 1, odfn[ou], -x});
  156.             vqry.push_back({1, tc, ed[u] + 1, oed[ou] + 1, +x});
  157.         }
  158.     }
  159.     rep(i, vqry.size()) vqry[i].pos = i;
  160.     conq(0, (int) vqry.size());
  161.     rep(i, q) if (is_qry[i]) printf("%lld\n", ans[i]);
  162.     return 0;
  163. }
  164.  
Success #stdin #stdout 0.01s 28708KB
comments (?)
stdin
copy 
10 20
100 0 0 0 0 0 0 0 0 0
1 2 8
2 3 3
2 4 5
2 5 2
5 6 3
5 7 5
1 8 2
1 9 4
9 10 1
2 1 3 1
2 2 2 2
1 8
2 4 1 8
1 8
1 1
2 10 5 1
1 4
2 20 2 1
2 40 4 5
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
stdout
copy 
0 1 10 8 8
1 2 7 9 9
2 3 3 12 12
3 4 4 10 10
4 5 7 15 15
5 6 6 17 17
6 7 7 16 16
7 8 8 18 18
8 9 10 11 11
9 10 10 19 19
10 0 0 7 9
11 0 0 14 16
12 0 0 6 10
13 0 0 5 11
14 0 0 13 17
15 0 0 4 12
16 0 0 3 17
17 0 0 2 18
18 0 0 1 19
0 15
1 17
7 18
0 12
0 17
4 11
0
4
101
13
131
33
23
33
62
22
62
24
21
0
https://ideone.com/lNSz3Q
language:
C++14 (gcc 8.3)
created:
4 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!