p2590&bzoj1036 树的统计
题目
一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. 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
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
1
2
2
10
6
5
6
5
16
分析
树剖裸题,没啥好说......
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const long long inf=1e18+7;
struct node {
long long sum,maxn;
}d[440000];
long long son[110000],fa[110000],acc[110000],dep[110000];
long long no[110000],size[110000],fin[110000],cnt,n;
vector<long long>v[40000];
char s[100];
void dfs1(long long x,long long f){
long long i,j,k,n=0;
size[x]=1;
for(i=0;i<v[x].size();i++)
if(v[x][i]!=f){
dep[v[x][i]]=dep[x]+1;
fa[v[x][i]]=x;
dfs1(v[x][i],x);
size[x]+=size[v[x][i]];
if(size[v[x][i]]>n){
n=size[v[x][i]];
son[x]=v[x][i];
}
}
return;
}
void dfs2(long long x,long long ac){
no[x]=++cnt;
acc[x]=ac;
long long i,j,k;
if(!son[x])return;
dfs2(son[x],ac);
for(i=0;i<v[x].size();i++)
if(v[x][i]!=fa[x]&&v[x][i]!=son[x])
dfs2(v[x][i],v[x][i]);
return;
}
void build(long long le,long long ri,long long wh,long long pos,long long k){
if(le==ri){
d[wh].sum=d[wh].maxn=k;
return;
}
d[wh].sum+=k;
d[wh].maxn=max(d[wh].maxn,k);
long long mid=(le+ri)>>1;
if(mid>=pos)build(le,mid,wh*2,pos,k);
else build(mid+1,ri,wh*2+1,pos,k);
}
void update(long long le,long long ri,long long wh,long long pos,long long k){
if(le==ri){
d[wh].sum=d[wh].maxn=k;
return;
}
long long mid=(le+ri)>>1;
if(mid>=pos){
update(le,mid,wh*2,pos,k);
d[wh].sum=d[wh*2].sum+d[wh*2+1].sum;
d[wh].maxn=max(d[wh*2+1].maxn,d[wh*2].maxn);
}else {
update(mid+1,ri,wh*2+1,pos,k);
d[wh].sum=d[wh*2].sum+d[wh*2+1].sum;
d[wh].maxn=max(d[wh*2+1].maxn,d[wh*2].maxn);
}
}
long long qmax(long long le,long long ri,long long x,long long y,long long wh){
if(le>=x&&ri<=y)return d[wh].maxn;
long long mid=(le+ri)>>1,ans=-inf;
if(x<=mid)ans=max(ans,qmax(le,mid,x,y,wh*2));
if(mid<y)ans=max(ans,qmax(mid+1,ri,x,y,wh*2+1));
return ans;
}
long long qsum(long long le,long long ri,long long x,long long y,long long wh){
if(le>=x&&ri<=y)return d[wh].sum;
long long mid=(le+ri)>>1,ans=0;
if(x<=mid)ans+=qsum(le,mid,x,y,wh*2);
if(mid<y)ans+=qsum(mid+1,ri,x,y,wh*2+1);
return ans;
}
long long que1(long long x,long long y){
long long ans=-inf;
while(acc[x]!=acc[y]){
if(dep[acc[x]]<dep[acc[y]])swap(x,y);
ans=max(ans,qmax(1,n,no[acc[x]],no[x],1));
x=fa[acc[x]];
}
if(no[x]>no[y])swap(x,y);
ans=max(ans,qmax(1,n,no[x],no[y],1));
return ans;
}
long long que2(long long x,long long y){
long long ans=0;
while(acc[x]!=acc[y]){
if(dep[acc[x]]<dep[acc[y]])swap(x,y);
ans+=qsum(1,n,no[acc[x]],no[x],1);
x=fa[acc[x]];
}
if(no[x]>no[y])swap(x,y);
ans+=qsum(1,n,no[x],no[y],1);
return ans;
}
int main()
{ long long m,i,j,k,x,y;
for(i=1;i<=440000;i++){
d[i].maxn=-inf;
d[i].sum=0;
}
scanf("%lld",&n);
for(i=1;i<n;i++){
scanf("%lld%lld",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dep[1]=1;
dfs1(1,0);
dfs2(1,1);
for(i=1;i<=n;i++){
scanf("%lld",&x);
build(1,n,1,no[i],x);
}
scanf("%lld",&m);
for(i=1;i<=m;i++){
scanf("%s",s);
if(s[0]=='C'){
scanf("%lld%lld",&x,&y);
update(1,n,1,no[x],y);
}else if(s[0]=='Q'&&s[1]=='M'){
scanf("%lld%lld",&x,&y);
printf("%lld\n",que1(x,y));
}else {
scanf("%lld%lld",&x,&y);
printf("%lld\n",que2(x,y));
}
}
return 0;
}
最新文章
- js instanceof
- ERROR! MySQL is running but PID file could not be found
- HTTP协议(转)
- acl拒绝访问流量
- Java Serializable(序列化)
- Flume-NG + HDFS + HIVE日志收集分析
- p标签中的span标签文字垂直居中对齐
- 三星Galaxy Note 10.1 N8010 最后的救赎 Andorid 5.0.2 ROM
- 20160205.CCPP体系详解(0015天)
- 【转载】MySQL 5.6主从Slave_IO_Running:Connecting/error connecting to master *- retry
- Eclipse换背景
- MYSQL 数据库导入导出命令
- 原根求解算法 &;&; NTT算法
- 关于input 的选中,自定义input[type=";checkbox";]样式
- 学习熟悉箭头函数, 类, 模板字面量, let和const声明
- Json工具类JsonUtil
- SQL Server 排名函数( ROW_NUMBER、RANK、DENSE_RANK、NTILE )
- POJ-1887 Testing the CATCHER(dp,最长下降子序列)
- APP案例分析-热血江湖
- [ 转载 ] Java基础12--基础学习总结——数组
热门文章
- Java多线程系列 面试题
- [原创]Scala学习:关于变量(val,var,类型推断)
- 算法(Algorithms)第4版 练习 1.3.2
- TCP/IP 协议中的编址
- Windows默认字符集_查询
- web项目中添加logger日志
- spring boot: 在maven中装入springframework框架
- idea集成spring+spring MVC+mybatis问题
- linux 替换目录下文件所有关键字
- python 链接MS SQL