題面

戳我

Sol

動態點分治：
建個點分樹，每個節點開兩顆線段樹，以與該點的距離為下標，維護價值和
一棵樹維護這個點的，一棵維護對上層重心的貢獻

然后。。
然后？直接暴力搞就行了

注意常數優化我TLE了一遍，第二遍卡過去的

# include <bits/stdc++.h> # define RG register # define IL inline # define Fill(a, b) memset(a, b, sizeof(a)) using namespace std; typedef long long ll; const int _(2e5 + 10), __(2e7 + 10);IL ll Read(){RG ll x = 0, z = 1; RG char c = getchar();for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);return x * z; }int n, fst[_], nxt[_], w[_], to[_], cnt, Q;IL void Add(RG int u, RG int v){ nxt[cnt] = fst[u]; to[cnt] = v; fst[u] = cnt++; }namespace ChainDiv{int fa[_], size[_], top[_], deep[_], son[_], dfn[_], Index;IL void Dfs1(RG int u){size[u] = 1;for(RG int e = fst[u]; e != -1; e = nxt[e]){if(size[to[e]]) continue;deep[to[e]] = deep[u] + 1; fa[to[e]] = u;Dfs1(to[e]);size[u] += size[to[e]];if(size[to[e]] > size[son[u]]) son[u] = to[e];}}IL void Dfs2(RG int u, RG int Top){top[u] = Top; dfn[u] = ++Index;if(son[u]) Dfs2(son[u], Top);for(RG int e = fst[u]; e != -1; e = nxt[e]) if(!dfn[to[e]]) Dfs2(to[e], to[e]);}IL ll Dis(RG int u, RG int v){RG ll dis = deep[u] + deep[v];while(top[u] ^ top[v]){ if(deep[top[u]] < deep[top[v]]) swap(u, v); u = fa[top[u]]; }if(deep[u] > deep[v]) swap(u, v);return dis - 2 * deep[u];} }int rot[_], ls[__], rs[__], sum[__], tot; int size[_], mx[_], frt[_], vis[_], rt, sz, root;IL void Getroot(RG int u, RG int ff){size[u] = 1; mx[u] = 0;for(RG int e = fst[u]; e != -1; e = nxt[e]){if(vis[to[e]] || to[e] == ff) continue;Getroot(to[e], u);size[u] += size[to[e]];mx[u] = max(mx[u], size[to[e]]);}mx[u] = max(mx[u], sz - size[u]);if(mx[u] < mx[rt]) rt = u; }IL void Create(RG int u, RG int ff){frt[u] = ff; vis[u] = 1;for(RG int e = fst[u]; e != -1; e = nxt[e]){if(vis[to[e]]) continue;rt = 0; sz = size[to[e]];Getroot(to[e], u); Create(rt, u);} }IL void Update(RG int &x, RG int l, RG int r, RG int pos, RG int d){if(!x) x = ++tot; sum[x] += d;if(l == r) return;RG int mid = (l + r) >> 1;if(pos <= mid) Update(ls[x], l, mid, pos, d);else Update(rs[x], mid + 1, r, pos, d); }IL int Sum(RG int x, RG int l, RG int r, RG int k){if(!x) return 0;if(k >= r) return sum[x];RG int mid = (l + r) >> 1;if(k > mid) return sum[ls[x]] + Sum(rs[x], mid + 1, r, k);return Sum(ls[x], l, mid, k); }IL void Modify(RG int u, RG int d){Update(rot[u], 0, n - 1, 0, d);for(RG int v = u, dis; frt[v]; v = frt[v]){dis = ChainDiv::Dis(frt[v], u);Update(rot[frt[v]], 0, n - 1, dis, d);Update(rot[v + n], 0, n - 1, dis, d);} }IL int Query(RG int u, RG int k){RG int ans = Sum(rot[u], 0, n - 1, k);for(RG int v = u, dis; frt[v]; v = frt[v]){dis = ChainDiv::Dis(frt[v], u);if(k < dis) continue;ans += Sum(rot[frt[v]], 0, n - 1, k - dis);ans -= Sum(rot[v + n], 0, n - 1, k - dis);}return ans; }int main(RG int argc, RG char* argv[]){sz = n = Read(); Q = Read(); Fill(fst, -1);for(RG int i = 1; i <= n; ++i) w[i] = Read();for(RG int i = 1, a, b; i < n; ++i) a = Read(), b = Read(), Add(a, b), Add(b, a);ChainDiv::Dfs1(1); ChainDiv::Dfs2(1, 1);mx[0] = n + 1; cnt = 0;Getroot(1, 0); root = rt; Create(rt, 0);for(RG int i = 1; i <= n; ++i) Modify(i, w[i]);for(RG int ans = 0; Q; --Q){RG int op = Read(), x = Read() ^ ans, y = Read() ^ ans;if(!op) printf("%d\n", ans = Query(x, y));else Modify(x, y - w[x]), w[x] = y;}return 0; }

總結

以上是生活随笔為你收集整理的Bzoj3730: 震波的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。