LOJ #6208. 树上询问

题目链接：​​传送门​​

线段树维护每个点的k,t,d

当做懒标记来维护

这就需要对懒标记的理解了

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
namespace Seg {
  struct node {int l, r, k, d, w, f;}tree[A];
  void build(int k, int l, int r) {
    tree[k].l = l; tree[k].r = r;
    if (l == r) return;
    int m = (l + r) >> 1;
    build(k << 1, l, m); build(k << 1 | 1, m + 1, r);
  }
  void down(int k) {
    tree[k << 1].w += tree[k].w + tree[k << 1].k * tree[k].d;
    tree[k << 1 | 1].w += tree[k].w + tree[k << 1 | 1].k * tree[k].d;
    tree[k << 1].k += tree[k].k; tree[k << 1 | 1].k += tree[k].k;
    tree[k << 1].d += tree[k].d; tree[k << 1 | 1].d += tree[k].d;
    tree[k].w = tree[k].k = tree[k].d = 0;
  }
  void change1(int k, int l, int r, int val) {
    if (tree[k].l >= l and tree[k].r <= r) {tree[k].k += val; return;}
    int m = (tree[k].l + tree[k].r) >> 1; down(k);
    if (l <= m) change1(k << 1, l, r, val);
    if (r > m) change1(k << 1 | 1, l, r, val);
  }
  void change2(int k, int l, int r, int val) {
    if (tree[k].l >= l and tree[k].r <= r) {tree[k].d += val; tree[k].w += tree[k].k * val; return;}
    int m = (tree[k].l + tree[k].r) >> 1; down(k);
    if (l <= m) change2(k << 1, l, r, val);
    if (r > m) change2(k << 1 | 1, l, r, val);
  }
  int ask(int k, int pos) {
    if (tree[k].l == tree[k].r) return tree[k].w;
    int m = (tree[k].l + tree[k].r) >> 1; down(k);
    if (pos <= m) return ask(k << 1, pos);
    else return ask(k << 1 | 1, pos);
  }
}
int dfn[A];
namespace Cut {
  struct node {int next, to;}e[A];
  int head[A], num;
  int siz[A], fa[A], dep[A], son[A], top[A], cnt;
  void add(int fr, int to) {e[++num].next = head[fr]; e[num].to = to; head[fr] = num;
    swap(fr, to); e[++num].next = head[fr]; e[num].to = to; head[fr] = num;}
  void prepare(int fr) {
    siz[fr] = 1;
    for (int i = head[fr]; i; i = e[i].next) {
      int ca = e[i].to;
      if (ca == fa[fr]) continue;
      fa[ca] = fr; dep[ca] = dep[fr] + 1;
      prepare(ca); siz[fr] += siz[ca];
      if (siz[ca] > siz[son[fr]]) son[fr] = ca;
    }
  }
  void dfs(int fr, int tp) {
    dfn[fr] = ++cnt; top[fr] = tp;
    if (son[fr]) dfs(son[fr], tp);
    for (int i = head[fr]; i; i = e[i].next) {
      int ca = e[i].to;
      if (ca == fa[fr] or ca == son[fr]) continue;
      dfs(ca, ca);
    }
  }
  void change1(int x, int y, int val) {
    while (top[x] != top[y]) {
      if (dep[top[x]] < dep[top[y]]) swap(x, y);
      Seg::change1(1, dfn[top[x]], dfn[x], val);
      x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    Seg::change1(1, dfn[x], dfn[y], val);
  }
  void change2(int x, int y, int val) {
    while (top[x] != top[y]) {
      if (dep[top[x]] < dep[top[y]]) swap(x, y);
      Seg::change2(1, dfn[top[x]], dfn[x], val);
      x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    Seg::change2(1, dfn[x], dfn[y], val);
  }
}
int n, m, a, b, opt;

int main(int argc, char const *argv[]) {
  cin >> n;
  for (int i = 2; i <= n; i++) scanf("%d%d", &a, &b), Cut::add(a, b);
  cin >> m; Cut::prepare(1); Cut::dfs(1, 1); Seg::build(1, 1, n);
  while (m--) {
    scanf("%d", &opt);
    if (opt == 1) scanf("%d%d", &a, &b), Cut::change1(1, a, b);
    if (opt == 2) scanf("%d%d", &a, &b), Cut::change2(1, a, b);
    if (opt == 3) scanf("%d", &a), printf("%d\n", Seg::ask(1, dfn[a]));
  }
}