题意:
给出一棵树,每个顶点上有一个权值。
操作:选择一条路径,并将路径上所有的点的权值同时加或减某个数。
查询:某个点的当前权值
分析:
树链剖分完毕后,就是简单的线段树区间更新。
提交的时候注意要要加一句扩栈的代码,用C++提交。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; void read(int& x) {
x = ;
char c = ' ';
while(c < '' || c > '') c = getchar();
while('' <= c && c <= '') {
x = x * + c - '';
c = getchar();
}
} const int maxn = + ;
const int maxnode = maxn * ; struct Edge
{
int v, nxt;
Edge() {}
Edge(int v, int nxt) :v(v), nxt(nxt) {}
}; int n, m, q;
int a[maxn]; int ecnt, head[maxn];
Edge edges[maxn * ]; void AddEdge(int u, int v) {
edges[++ecnt] = Edge(v, head[u]);
head[u] = ecnt;
edges[++ecnt] = Edge(u, head[v]);
head[v] = ecnt;
} int dep[maxn], fa[maxn], son[maxn], sz[maxn]; int tot, id[maxn], pos[maxn], top[maxn]; void dfs(int u) {
sz[u] = ; son[u] = -;
for(int i = head[u]; i; i = edges[i].nxt) {
int v = edges[i].v;
if(v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + ;
dfs(v);
sz[u] += sz[v];
if(son[u] == - || sz[v] > sz[son[u]]) son[u] = v;
}
} void dfs2(int u, int tp) {
top[u] = tp;
id[u] = ++tot;
pos[tot] = u;
if(son[u] == -) return;
if(son[u]) dfs2(son[u], tp);
for(int i = head[u]; i; i = edges[i].nxt) {
int v = edges[i].v;
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
} int sumv[maxnode], addv[maxnode];
char cmd[]; void pushup(int o) { sumv[o] = sumv[o<<] + sumv[o<<|]; } void build(int o, int L, int R) {
if(L == R) { sumv[o] = a[pos[L]]; return; }
int M = (L + R) / ;
build(o<<, L, M);
build(o<<|, M+, R);
pushup(o);
} void pushdown(int o, int L, int R) {
if(addv[o]) {
addv[o<<] += addv[o];
addv[o<<|] += addv[o];
int M = (L + R) / ;
sumv[o<<] += (M - L + ) * addv[o];
sumv[o<<|] += (R - M) * addv[o];
addv[o] = ;
}
} void update(int o, int L, int R, int qL, int qR, int v) {
if(qL <= L && R <= qR) {
sumv[o] += (R - L + ) * v;
addv[o] += v;
return;
}
pushdown(o, L, R);
int M = (L + R) / ;
if(qL <= M) update(o<<, L, M, qL, qR, v);
if(qR > M) update(o<<|, M+, R, qL, qR, v);
pushup(o);
} void UPDATE(int u, int v, int val) {
int t1 = top[u], t2 = top[v];
while(t1 != t2) {
if(dep[t1] < dep[t2]) { swap(u, v); swap(t1, t2); }
update(, , n, id[t1], id[u], val);
u = fa[t1]; t1 = top[u];
}
if(dep[u] > dep[v]) swap(u, v);
update(, , n, id[u], id[v], val);
} int query(int o, int L, int R, int p) {
if(L == R) return sumv[o];
pushdown(o, L, R);
int M = (L + R) / ;
if(p <= M) return query(o<<, L, M, p);
else return query(o<<|, M+, R, p);
} int main()
{
while(scanf("%d%d%d", &n, &m, &q) == ) {
for(int i = ; i <= n; i++) read(a[i]); memset(head, , sizeof(head));
ecnt = ;
for(int i = ; i < n; i++) {
int u, v; read(u); read(v);
AddEdge(u, v);
} dfs();
tot = ;
dfs2(, ); memset(addv, , sizeof(addv));
build(, , n); while(q--) {
scanf("%s", cmd);
int u, v, d;
read(u);
if(cmd[] == 'Q') {
printf("%d\n", query(, , n, id[u]));
} else {
read(v); read(d);
if(cmd[] == 'D') d = -d;
UPDATE(u, v, d);
}
}
} return ;
}
代码君