采蘑菇的克拉莉絲

一個有點意思的樹鏈剖分的題。

題意：

一棵樹，有兩種操作：

①：在點$v$放$x$個蘑菇。

②：將起點變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$v$。

每次計算收集所有蘑菇的代價。

收集蘑菇的代價為，起點到所在蘑菇的路徑上的第一條邊的權(quán)值，也就是與起點直接相連的邊的權(quán)值。

做法：

選定$1$號節(jié)點為根節(jié)點，

考慮樹鏈剖分，對于更新操作，我們更新從$v?>1$的所有重鏈上的蘑菇數(shù)量，在輕鏈與重鏈的連接處，直接統(tǒng)計輕鏈對當前節(jié)點的貢獻即可。

查詢時，我們只需要查詢重兒子上的蘑菇的數(shù)量然后乘上邊權(quán)，再加上當前節(jié)點的輕鏈對其貢獻（之前統(tǒng)計過的），然后再得到其父節(jié)點的連通塊的答案即可。

#include <bits/stdc++.h>using namespace std;typedef long long ll; typedef pair<ll, ll> pll;const int N = 1e6 + 10;int head[N], to[N << 1], nex[N << 1], value[N << 1], cnt = 1;int n, m, fv[N];int dep[N], fa[N], sz[N], top[N], rk[N], id[N], son[N], tot;ll sum, tree[N << 2], lazy[N << 2], num[N];pll ans[N];inline void add(int x, int y, int w) {to[cnt] = y;nex[cnt] = head[x];value[cnt] = w;head[x] = cnt++; } void dfs1(int rt, int f) {fa[rt] = f, dep[rt] = dep[f] + 1, sz[rt] = 1;for (int i = head[rt]; i; i = nex[i]) {if (to[i] == f) {continue;}dfs1(to[i], rt);fv[to[i]] = value[i];sz[rt] += sz[to[i]];if (sz[son[rt]] < sz[to[i]]) {son[rt] = to[i];}} }void dfs2(int rt, int tp) {top[rt] = tp, rk[++tot] = rt, id[rt] = tot;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i = head[rt]; i; i = nex[i]) {if (to[i] == fa[rt] || to[i] == son[rt]) {continue;}dfs2(to[i], to[i]);} }void push_down(int rt) {if (lazy[rt]) {lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] += lazy[rt];tree[rt << 1] += lazy[rt], tree[rt << 1 | 1] += lazy[rt];lazy[rt] = 0;} }void update(int rt, int l, int r, int L, int R, int x) {if (l >= L && r <= R) {lazy[rt] += x;tree[rt] += x;return ;}push_down(rt);int mid = l + r >> 1;if (L <= mid) {update(rt << 1, l, mid, L, R, x);}if (R > mid) {update(rt << 1 | 1, mid + 1, r, L, R, x);} }ll query(int rt, int l, int r, int x) {if (l == r) {return tree[rt];}push_down(rt);int mid = l + r >> 1;if (x <= mid) {return query(rt << 1, l, mid, x);}else {return query(rt << 1 | 1, mid + 1, r, x);} }void solve(int v, int x) {while (v) {update(1, 1, n, id[top[v]], id[v], x);v = top[v];ans[fa[v]].first += 1ll * x * fv[v];ans[fa[v]].second += x;v = fa[v];} }ll get_ans(int v) {ll res = 0, cur = 0;if (son[v]) {cur = query(1, 1, n, id[son[v]]);}res += fv[son[v]] * cur;res += ans[v].first;res += fv[v] * (sum - cur - ans[v].second - num[v]);return res; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d", &n);for (int i = 1, x, y, w; i < n; i++) {scanf("%d %d %d", &x, &y, &w);add(x, y, w);add(y, x, w);}dfs1(1, 0);dfs2(1, 1);scanf("%d", &m);for (int i = 1, op, v, x, rt = 1; i <= m; i++) {scanf("%d %d", &op, &v);if (op & 1) {scanf("%d", &x);sum += x;num[v] += x;solve(v, x);}else {rt = v;}printf("%lld\n", get_ans(rt));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的采蘑菇的克拉莉丝（树链剖分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。