树链剖分+线段树 BZOJ 1036 [ZJOI2008]树的统计Count
2024-03-28 11:45:16
题意： I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身
分析：树链剖分第一题，把树拆成一条条链，有重链和轻链，每个点有转换后的新的位置，同一条链是线性的区间，这样可以用线段树进行操作。第一个是单点更新，第二个先求LCA，然后把u和v移动到lca所在的链，转移一次都是转移链，区间询问最大值和总和，第三种类似。
#include <bits/stdc++.h> const int N = 3e4 + 5;
const int D = 20;
const int INF = 0x7fffffff;
struct Edge {
int v, nex;
}edge[N<<1];
int head[N];
int a[N];
int sz[N], dep[N], belong[N], pos[N];
int rt[N][D];
int n, tote, loc; void add_edge(int u, int v) {
edge[tote].v = v; edge[tote].nex = head[u];
head[u] = tote++;
} void init_edge() {
memset (head, -1, sizeof (head));
tote = 0;
} void DFS1(int u, int fa) {
sz[u] = 1; dep[u] = dep[fa] + 1;
rt[u][0] = fa;
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v;
if (v == fa) {
continue;
}
DFS1 (v, u);
sz[u] += sz[v];
}
} void DFS2(int u, int fa, int chain) {
int k = 0;
pos[u] = ++loc;
belong[u] = chain;
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v;
if (v == fa) {
continue;
}
if (sz[v] > sz[k]) {
k = v;
}
}
if (k == 0) {
return ;
}
DFS2 (k, u, chain);
for (int i=head[u]; ~i; i=edge[i].nex) {
int v = edge[i].v;
if (v == fa || v == k) {
continue;
}
DFS2 (v, u, v);
}
} void init_LCA() {
for (int j=1; j<D; ++j) {
for (int i=1; i<=n; ++i) {
rt[i][j] = rt[i][j-1] == 0 ? 0 : rt[rt[i][j-1]][j-1];
}
}
} int LCA(int u, int v) {
if (dep[u] < dep[v]) {
std::swap (u, v);
}
for (int i=0; i<D; ++i) {
if ((dep[u] - dep[v]) >> i & 1) {
u = rt[u][i];
}
}
if (u == v) {
return u;
}
for (int i=D-1; i>=0; --i) {
if (rt[u][i] != rt[v][i]) {
u = rt[u][i];
v = rt[v][i];
}
}
return rt[u][0];
} int mx[N<<2], sum[N<<2]; #define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1 void push_up(int o) {
mx[o] = std::max (mx[o<<1], mx[o<<1|1]);
sum[o] = sum[o<<1] + sum[o<<1|1];
} void updata(int p, int v, int l, int r, int o) {
if (l == r) {
mx[o] = sum[o] = v;
return ;
}
int mid = l + r >> 1;
if (p <= mid) {
updata (p, v, lson);
} else {
updata (p, v, rson);
}
push_up (o);
} int query_max(int ql, int qr, int l, int r, int o) {
if (ql <= l && r <= qr) {
return mx[o];
}
int mid = l + r >> 1, ret = -INF;
if (ql <= mid) {
ret = std::max (ret, query_max (ql, qr, lson));
}
if (qr > mid) {
ret = std::max (ret, query_max (ql, qr, rson));
}
return ret;
} int query_sum(int ql, int qr, int l, int r, int o) {
if (ql <= l && r <= qr) {
return sum[o];
}
int mid = l + r >> 1, ret = 0;
if (ql <= mid) {
ret += query_sum (ql, qr, lson);
}
if (qr > mid) {
ret += query_sum (ql, qr, rson);
}
return ret;
} int get_sum(int u, int lca) {
int ret = 0;
while (belong[u] != belong[lca]) {
ret += query_sum (pos[belong[u]], pos[u], 1, n, 1);
u = rt[belong[u]][0];
}
ret += query_sum (pos[lca], pos[u], 1, n, 1);
return ret;
} int get_max(int u, int lca) {
int ret = -INF;
while (belong[u] != belong[lca]) {
ret = std::max (ret, query_max (pos[belong[u]], pos[u], 1, n, 1));
u = rt[belong[u]][0];
}
ret = std::max (ret, query_max (pos[lca], pos[u], 1, n, 1));
return ret;
} void prepare() {
sz[0] = 0; dep[0] = 0;
DFS1 (1, 0);
loc = 0;
DFS2 (1, 0, 1);
init_LCA ();
for (int i=1; i<=n; ++i) {
updata (pos[i], a[i], 1, n, 1);
}
} int main() {
scanf ("%d", &n);
init_edge ();
for (int i=1; i<n; ++i) {
int u, v;
scanf ("%d%d", &u, &v);
add_edge (u, v);
add_edge (v, u);
}
for (int i=1; i<=n; ++i) {
scanf ("%d", a+i);
} prepare (); int q;
scanf ("%d", &q);
char ch[6];
int x, y;
while (q--) {
scanf ("%s%d%d", ch, &x, &y);
if (ch[0] == 'C') {
a[x] = y;
updata (pos[x], a[x], 1, n, 1);
} else {
int lca = LCA (x, y);
if (ch[1] == 'M') {
printf ("%d\n", std::max (get_max (x, lca), get_max (y, lca)));
} else {
printf ("%d\n", get_sum (x, lca) + get_sum (y, lca) - a[lca]);
}
}
}
return 0;
}
最新文章
- python---socketserver模块
- iOS开发中如何使自定义方法具有XCode插件使用提示
- SQL Server 2000： 维护计划无法执行
- 6 this的使用方法
- bitmap格式分析
- Javascript事件处理进阶
- SC命令执行出现Access is denied
- MST(Kruskal’s Minimum Spanning Tree Algorithm)
- mysql Encryption and Compression Functions
- Android 自定义UI--指南针
- C语言字符串操作函数
- iOS执行时与method swizzling
- Hadoop查看目录文件大小的脚本
- .NET（C#、VB）APP开发——Smobiler平台控件介绍：SliderView控件
- URL和URI以及两者的区别和联系
- Linux c使用gumbo库解析页面表单信息（三）
- Java并发编程实战
- linux中fork, source和exec的区别
- django序列化 serializers
- 转：display：flex不兼容Android、Safari低版本的解决方案 【flex布局】