bzoj4034

2019-11-06 06:35:35

字体：大中小

来源：转载

供稿：网友

#include <cstdio>#include <cstring>#include <algorithm>#include <vector>typedef long long ll;typedef const int cint;typedef const long long cll;template <typename tp>inline void readln(tp &x) { register char ch; register bool nega; x = nega = 0; for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) nega |= (ch == '-'); for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; if (nega) x = -x;}class SegTree {PRivate: struct SegTNode { int l, r; ll sum, tag; SegTNode() { sum = tag = 0; } }tr[100005 << 2]; #define mid ((l + r) >> 1) void Build(cint &k, cint &l, cint &r) { tr[k].l = l, tr[k].r = r; if (l == r) return; Build(k << 1, l, mid); Build(k << 1 | 1, mid + 1, r); } inline void DownTag(cint &k) { tr[k << 1].tag += tr[k].tag; tr[k << 1].sum += tr[k].tag * (tr[k << 1].r - tr[k << 1].l + 1ll); tr[k << 1 | 1].tag += tr[k].tag; tr[k << 1 | 1].sum += tr[k].tag * (tr[k << 1 | 1].r - tr[k << 1 | 1].l + 1ll); tr[k].tag = 0; } void Add(cint &k, cint &L, cint &R, cll &x) { int l = tr[k].l, r = tr[k].r; if (L <= l && r <= R) { tr[k].tag += x; tr[k].sum += x * (r - l + 1ll); return; } if (tr[k].tag) DownTag(k); if (L <= mid) Add(k << 1, L, R, x); if (mid < R) Add(k << 1 | 1, L, R, x); tr[k].sum = tr[k << 1].sum + tr[k << 1 | 1].sum; } ll Query(cint &k, cint &L, cint &R) { int l = tr[k].l, r = tr[k].r; if (L <= l && r <= R) return tr[k].sum; if (tr[k].tag) DownTag(k); ll ret = 0; if (L <= mid) ret += Query(k << 1, L, R); if (mid < R) ret += Query(k << 1 | 1, L, R); return ret; } #undef midpublic: inline void build(cint &l, cint &r) { Build(1, l, r); } inline void add(cint &l, cint &r, cll &x) { Add(1, l, r, x); } inline void add(cint &a, cll &x) { Add(1, a, a, x); } inline ll query(cint &l, cint &r) { return Query(1, l, r); }}SegT;int n, m;int sz[100005], fa[100005], son[100005], top[100005], order[100005], tot = 0;std::vector<int> to[100005];#define next to[nowp][i]int DFS(cint &nowp) { int tmp, maxson = 0; sz[nowp] = 1; for (unsigned i = 0; i < to[nowp].size(); i++) { if (next == fa[nowp]) continue; fa[next] = nowp; sz[nowp] += (tmp = DFS(next)); if (tmp > maxson) { maxson = tmp; son[nowp] = next; } } return sz[nowp];}void DFS2(cint &nowp, cint &Top) { if (!nowp) return; top[nowp] = Top; order[nowp] = ++tot; DFS2(son[nowp], Top); for (unsigned i = 0; i < to[nowp].size(); i++) { if (next == fa[nowp] || next == son[nowp]) continue; DFS2(next, next); }}#undef nextinline ll Calc(int x) { ll ret = 0; while (top[x] != 1) { ret += SegT.query(order[top[x]], order[x]); x = fa[top[x]]; } ret += SegT.query(1, order[x]); return ret;}inline void Init() { int u, v; readln(n); readln(m); ll w[n + 1]; for (int i = 1; i <= n; i++) readln(w[i]); for (int i = 1; i < n; i++) { readln(u); readln(v); to[u].push_back(v); to[v].push_back(u); } DFS(1); DFS2(1, 1); SegT.build(1, n); for (int i = 1; i <= n; i++) SegT.add(order[i], w[i]);}inline void Solve() { int opt, x; ll a; while (m--) { readln(opt); readln(x); switch (opt) { case 1: readln(a); SegT.add(order[x], a); break; case 2: readln(a); SegT.add(order[x], order[x] + sz[x] - 1, a); break; case 3: printf("%I64d/n", Calc(x)); } }}int main() { Init(); Solve(); return 0;}

//bzoj4034

上一篇：hdu 1024 Max Sum Plus Plus

下一篇：算法提高金陵十三钗状压DP