1036: [ZJOI2008]树的统计Count(树链剖分)
2024-09-03 09:48:37
1036: [ZJOI2008]树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 19830 Solved: 8067
[Submit][Status][Discuss]
Description
一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成
一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意:从点u到点v的路径上的节点包括u和v本身
Input
输入的第一行为一个整数n,表示节点的个数。接下来n – 1行,每行2个整数a和b,表示节点a和节点b之间有
一条边相连。接下来n行,每行一个整数,第i行的整数wi表示节点i的权值。接下来1行,为一个整数q,表示操作
的总数。接下来q行,每行一个操作,以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
对于100%的数据,保证1<=n<=30000,0<=q<=200000;中途操作中保证每个节点的权值w在-30000到30000之间。
Output
对于每个“QMAX”或者“QSUM”的操作,每行输出一个整数表示要求输出的结果。
Sample Input
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
Sample Output
4
1
2
2
10
6
5
6
5
16
1
2
2
10
6
5
6
5
16
code
#include<cstdio>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 using namespace std; const int N = ; int sum[N<<],mx[N<<],w[N];
int bel[N],fa[N],son[N],siz[N],pos[N],deth[N],id[N];
struct Edge {
int nxt,to;
}e[];
int head[N],tot,tn; inline void add_edge(int u,int v) {
e[++tot].to = v,e[tot].nxt = head[u],head[u] = tot;
}
void dfs1(int u,int pa) {
siz[u] = ;
for (int i=head[u]; i; i=e[i].nxt) {
int v = e[i].to;
if (v==pa) continue;
deth[v] = deth[u] + ;
fa[v] = u;
dfs1(v,u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u,int top) {
pos[u] = ++tn;
id[tn] = u;
bel[u] = top;
if (!son[u]) return ;
dfs2(son[u],top);
for (int i=head[u]; i; i=e[i].nxt) {
int v = e[i].to;
if (v != son[u] && v != fa[u]) dfs2(v,v);
}
}
inline void pushup(int rt) {
sum[rt] = sum[rt<<] + sum[rt<<|];
mx[rt] = max(mx[rt<<],mx[rt<<|]);
}
void build(int l,int r,int rt) {
if (l==r) {
sum[rt] = mx[rt] = w[id[l]];
return ;
}
int m = (l + r) >> ;
build(lson);
build(rson);
pushup(rt);
}
void update(int l,int r,int rt,int p,int x) {
if (l==r) {
sum[rt] = mx[rt] = x;
return ;
}
int m = (l + r) >> ;
if (p <= m) update(lson,p,x);
else update(rson,p,x);
pushup(rt);
}
int query_sum(int l,int r,int rt,int L,int R) {
if (L <= l && r <= R) {
return sum[rt];
}
int m = (l + r) >> ,ret = ;
if (L <= m) ret += query_sum(lson,L,R);
if (R > m) ret += query_sum(rson,L,R);
return ret;
}
int query_max(int l,int r,int rt,int L,int R) {
if (L <= l && r <= R) {
return mx[rt];
}
int m = (l + r) >> ,ret = -1e9;
if (L <= m) ret = max(ret,query_max(lson,L,R));
if (R > m) ret = max(ret,query_max(rson,L,R));
return ret;
}
void work_sum(int x,int y) {
int ans = ;
while (bel[x] != bel[y]) {
if (deth[bel[x]] < deth[bel[y]]) swap(x,y);
ans += query_sum(,tn,,pos[bel[x]],pos[x]);
x = fa[bel[x]];
}
if (pos[x] > pos[y]) swap(x,y);
ans += query_sum(,tn,,pos[x],pos[y]);
printf("%d\n",ans);
}
void work_max(int x,int y) {
int ans = -1e9;
while (bel[x] != bel[y]) {
if (deth[bel[x]] < deth[bel[y]]) swap(x,y);
ans = max(ans,query_max(,tn,,pos[bel[x]],pos[x]));
x = fa[bel[x]];
}
if (pos[x] > pos[y]) swap(x,y);
ans = max(ans,query_max(,tn,,pos[x],pos[y]));
printf("%d\n",ans);
}
int main() {
int n,q,x,y;
scanf("%d",&n);
for (int a,b,i=; i<n; ++i) {
scanf("%d%d",&a,&b);
add_edge(a,b);add_edge(b,a);
}
for (int i=; i<=n; ++i) scanf("%d",&w[i]);
dfs1(,);
dfs2(,);
build(,tn,);
char opt[];
scanf("%d",&q);
while (q--) {
scanf("%s%d%d",opt,&x,&y);
if (opt[]=='C') w[x] = y,update(,tn,,pos[x],y);
else if (opt[]=='M') work_max(x,y);
else work_sum(x,y);
}
return ;
}
最新文章
- 谨慎DateTime.Now在EF的query中的使用
- 关于轻松安装LNMP和LAMP的编译环境
- Hacker Technology
- 使用AzCopy跨账户迁移blob
- 【美妙的Python之中的一个】Python简单介绍及环境搭建
- centos不能挂在ntfs
- SQLSERVER执行时间统计工具SQLQueryStress
- python求微分方程组的数值解曲线01
- Nopcommerce架构浅谈之架构层次
- hdu_5769_Substring(后缀数组)
- JAVA的免费天气api接口调用示例
- org.springframework.beans.factory.BeanDefinitionStoreException: Failed to read candidate component class: file [/Users/lonecloud/tomcat/apache-tomcat-7.0.70 2/webapps/myproject/WEB-INF/classes/cn/lone
- 仿EXCEL插件,智表ZCELL产品V1.5 版本发布,IE8/9完全兼容
- TCP/IP协议、UDP协议、 Http协议
- 采用NoteExpress参考文献导入和导出
- mysql-xtrabackup备份sh: xtrabackup_56: command not found与error while loading shared libraries: libssl.so.6: cannot open shared object file: No such file or directory
- 网易彩票-我的彩票-设置-cell跳转界面
- Linux编程 17 文件权限(权限设置chmod,改变文件属主属组关系chown,chgrp)
- Java多线程(二)关于多线程的CPU密集型和IO密集型这件事
- 9patch图的尺寸尽量为偶数