首页 > 代码库 > P2590 [ZJOI2008]树的统计
P2590 [ZJOI2008]树的统计
题目描述
一棵树上有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本身
输入输出格式
输入格式：
输入文件的第一行为一个整数n，表示节点的个数。
接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。
接下来一行n个整数，第i个整数wi表示节点i的权值。
接下来1行，为一个整数q，表示操作的总数。
接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
输出格式：
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。
输入输出样例
输入样例#1：
41 22 34 14 2 1 312QMAX 3 4QMAX 3 3QMAX 3 2QMAX 2 3QSUM 3 4QSUM 2 1CHANGE 1 5QMAX 3 4CHANGE 3 6QMAX 3 4QMAX 2 4QSUM 3 4
输出样例#1：
412210656516
说明
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
裸的树链剖分。
注意所有的值都要取最大或者最小。
有很小的负边权！
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define ls k<<1#define rs k<<1|1using namespace std;const int MAXN=1000001;inline void read(int &n){ char c=‘+‘;int x=0;bool flag=0; while(c<‘0‘||c>‘9‘) {c=getchar();if(c==‘-‘)flag=1;} while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48,c=getchar();} flag==1?n=-x:n=x;}int n;int a[MAXN];int fa[MAXN];// 每一个节点的父亲节点int deep[MAXN];// 每一个节点的深度int top[MAXN];// 重链上的顶节点int son[MAXN];// 每一个点的重儿子 int size[MAXN];// 子节点的数量int pos[MAXN];// 划分轻重链之后的编号int tot;// 总结点的数量 struct node{ int l,r,maxn,sum;}tree[MAXN];struct EDGE{ int u,v,nxt;}edge[MAXN];int head[MAXN];int num=1;//int nowmax=-1;int nowsum=0;void update(int k){ tree[k].maxn=max(tree[ls].maxn,tree[rs].maxn); tree[k].sum=(tree[ls].sum+tree[rs].sum);}void add_edge(int x,int y){ edge[num].u=x; edge[num].v=y; edge[num].nxt=head[x]; head[x]=num++;}int dfs1(int now,int nowfa,int nowdeep){ deep[now]=nowdeep; fa[now]=nowfa; size[now]=1; for(int i=head[now];i!=-1;i=edge[i].nxt) { if(edge[i].v!=nowfa) { dfs1(edge[i].v,now,nowdeep+1); size[now]+=size[edge[i].v]; if(son[now]==-1||size[edge[i].v]>size[son[now]]) son[now]=edge[i].v; } }}void dfs2(int now,int nowid){ tot++; pos[now]=tot;//更改当前节点的编号 top[now]=nowid; if(!son[now])// 没有重儿子 return ; dfs2(son[now],nowid);// 在一条重链上 for(int i=head[now];i!=-1;i=edge[i].nxt) if(deep[edge[i].v]>deep[edge[i].u]&&edge[i].v!=son[edge[i].u]) dfs2(edge[i].v,edge[i].v);//自己和自己一条重链 return ; }void build_tree(int k,int ll,int rr){ tree[k].l=ll;tree[k].r=rr; if(tree[k].l==tree[k].r) { tree[k].maxn=tree[k].sum=0; return ; } int mid=(ll+rr)>>1; build_tree(ls,ll,mid); build_tree(rs,mid+1,rr); update(k);}void insert(int k,int pos,int val){ if(tree[k].l==tree[k].r) { tree[k].maxn=tree[k].sum=val; return ; } int mid=(tree[k].l+tree[k].r)>>1; if(pos<=mid) insert(ls,pos,val); if(pos>mid) insert(rs,pos,val); update(k); }int querymax(int k,int ll,int rr){ if(ll<=tree[k].l&&tree[k].r<=rr) return tree[k].maxn; int mid=(tree[k].l+tree[k].r)>>1,nowmax=-1; if(ll<=mid) nowmax=max(nowmax,querymax(ls,ll,rr)); if(rr>mid) nowmax=max(nowmax,querymax(rs,ll,rr)); return nowmax;}int askmax(int u,int v){ int ans=-0x7ffff; while(top[u]!=top[v])//不在一条重链上 { if(deep[top[u]]<deep[top[v]]) swap(u,v); ans=max(ans,querymax(1,pos[top[u]],pos[u])); u=fa[top[u]]; } if(pos[u]>pos[v]) swap(u,v); ans=max(ans,querymax(1,pos[u],pos[v])); return ans;}int querysum(int k,int ll,int rr){ if(ll<=tree[k].l&&tree[k].r<=rr) return tree[k].sum; int mid=(tree[k].l+tree[k].r)>>1,nowsum=0; if(ll<=mid) nowsum+=querysum(ls,ll,rr); if(rr>mid) nowsum+=querysum(rs,ll,rr); return nowsum;}int asksum(int u,int v){ int ans=0; while(top[u]!=top[v]) { if(deep[top[u]]<deep[top[v]]) swap(u,v); ans+=querysum(1,pos[top[u]],pos[u]); u=fa[top[u]]; } if(pos[u]>pos[v]) swap(u,v); ans+=querysum(1,pos[u],pos[v]); return ans;}int main(){ ///freopen("bzoj_1036.in","r",stdin); //freopen("bzoj_1036.out","w",stdout); read(n); memset(head,-1,sizeof(head)); //memset(son,-1,sizeof(son)); for(int i=1;i<=n-1;i++) { int x,y; read(x);read(y); add_edge(x,y); add_edge(y,x); } for(int i=1;i<=n;i++) read(a[i]); dfs1(1,0,0); dfs2(1,1); build_tree(1,1,n); for(int i=1;i<=n;i++) insert(1,pos[i],a[i]); int q; read(q); for(int i=1;i<=q;i++) { string s; cin>>s; if(s[1]==‘H‘)// 修改 { int p,v; read(p);read(v); a[p]=v; insert(1,pos[p],v); } else if(s[1]==‘M‘)// 最大值 { int l,r; read(l);read(r); printf("%d\n",askmax(l,r)); } else//求和 { int l,r; read(l);read(r); printf("%d\n",asksum(l,r)); } } return 0;}
P2590 [ZJOI2008]树的统计
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。