鄂尔多斯网站开发,展示网站多少钱一个,wordpress文章页打不开了,网站建设编辑工作总结采蘑菇的克拉莉丝
一个有点意思的树链剖分的题。
题意#xff1a;
一棵树#xff0c;有两种操作#xff1a;
①#xff1a;在点vvv放xxx个蘑菇。
②#xff1a;将起点变为vvv。
每次计算收集所有蘑菇的代价。
收集蘑菇的代价为#xff0c;起点到所在蘑菇的路径上的…采蘑菇的克拉莉丝
一个有点意思的树链剖分的题。
题意
一棵树有两种操作
①在点vvv放xxx个蘑菇。
②将起点变为vvv。
每次计算收集所有蘑菇的代价。
收集蘑菇的代价为起点到所在蘑菇的路径上的第一条边的权值也就是与起点直接相连的边的权值。
做法
选定111号节点为根节点
考虑树链剖分对于更新操作我们更新从v−1v-1v−1的所有重链上的蘑菇数量在轻链与重链的连接处直接统计轻链对当前节点的贡献即可。
查询时我们只需要查询重儿子上的蘑菇的数量然后乘上边权再加上当前节点的轻链对其贡献之前统计过的然后再得到其父节点的连通块的答案即可。
#include bits/stdc.husing namespace std;typedef long long ll;
typedef pairll, 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;
}
