首页 > 代码库 > 洛谷 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 <ctype.h>#include <cstdio>#define N 50000void read(int &x){ x=0; bool f=0; char ch=getchar(); while(!isdigit(ch)) {if(ch==‘-‘) f=1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-‘0‘;ch=getchar();} x=f?(~x)+1:x;}struct Edge{ int next,to;}edge[N<<1];struct Tree{ int l,r,dis,Max; Tree *left,*right; Tree() { left=right=NULL; dis=Max=0; }}*root;int dfn[N],Q,dis[N],head[N],cnt,n,top[N],fa[N],dep[N],tim,size[N],belong[N];int max(int a,int b) {return a>b?a:b;} void add(int u,int v){ ++cnt; edge[cnt].next=head[u]; edge[cnt].to=v; head[u]=cnt;}void dfs1(int x){ size[x]=1; dep[x]=dep[fa[x]]+1; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(fa[x]!=v) { fa[v]=x; dfs1(v); size[x]+=size[v]; } }}void dfs2(int x){ belong[x]=++tim; dfn[tim]=x; int t=0; if(!top[x]) top[x]=x; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(fa[x]!=v&&size[t]<size[v]) t=v; } if(t) top[t]=top[x],dfs2(t); for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(fa[x]!=v&&v!=t) dfs2(v); }}void build(Tree *&k,int l,int r){ k=new Tree; k->l=l;k->r=r; if(l==r) { k->dis=k->Max=dis[dfn[l]]; return; } int mid=(l+r)>>1; build(k->left,l,mid); build(k->right,mid+1,r); k->dis=k->left->dis+k->right->dis; k->Max=max(k->left->Max,k->right->Max);}void Tree_change(Tree *&k,int t,int z){ if(k->l==k->r) { k->dis=k->Max=z; return; } int mid=(k->l+k->r)>>1; if(mid>=t) Tree_change(k->left,t,z); else Tree_change(k->right,t,z); k->dis=k->left->dis+k->right->dis; k->Max=max(k->left->Max,k->right->Max);}void swap(int &x,int &y){ int tmp=y; y=x; x=tmp;}int Tree_Query_Max(Tree *&k,int l,int r){ if(k->l==l&&k->r==r) return k->Max; int mid=(k->l+k->r)>>1; if(l>mid) return Tree_Query_Max(k->right,l,r); else if(r<=mid) return Tree_Query_Max(k->left,l,r); else return max(Tree_Query_Max(k->left,l,mid),Tree_Query_Max(k->right,mid+1,r));}int Chain_Query_Max(int x,int y){ int ans=-0x7fffffff; for(;top[x]!=top[y];x=fa[top[x]]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans=max(ans,Tree_Query_Max(root,belong[top[x]],belong[x])); } if(belong[x]>belong[y]) swap(x,y); ans=max(ans,Tree_Query_Max(root,belong[x],belong[y])); return ans;}int Tree_Query_Sum(Tree *&k,int l,int r){ if(k->l==l&&k->r==r) return k->dis; int mid=(k->l+k->r)>>1; if(l>mid) return Tree_Query_Sum(k->right,l,r); else if(r<=mid) return Tree_Query_Sum(k->left,l,r); else return Tree_Query_Sum(k->left,l,mid)+Tree_Query_Sum(k->right,mid+1,r);}int Chain_Query_Sum(int x,int y){ int ans=0; for(;top[x]!=top[y];x=fa[top[x]]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=Tree_Query_Sum(root,belong[top[x]],belong[x]); } if(belong[x]>belong[y]) swap(x,y); ans+=Tree_Query_Sum(root,belong[x],belong[y]); return ans;}int main(){ read(n); for(int a,b,i=1;i<n;i++) { read(a); read(b); add(a,b); add(b,a); } for(int i=1;i<=n;i++) read(dis[i]); dfs1(1); dfs2(1); read(Q); root=new Tree; build(root,1,n); char str[11]; for(int x,y;Q--;) { scanf("%s",str+1); if(str[1]==‘C‘) { read(x); read(y); Tree_change(root,belong[x],y); } else if(str[2]==‘M‘) { read(x); read(y); printf("%d\n",Chain_Query_Max(x,y)); } else { read(x); read(y); printf("%d\n",Chain_Query_Sum(x,y)); } } return 0;}
洛谷 P2590 [ZJOI2008]树的统计
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。