|
#define MAXN 200050 const int MAXN = 200050; //邻接表存树 struct edge{ int to; //边指向的顶点 int next; //下一条边在链表中的位置 }; vector<edge> es; int n,m,r,p,val[MAXN],u,v,x,y,z,c; int head[MAXN];//记录每个节点的边的链表表头 int size[MAXN],fa[MAXN],dep[MAXN],son[MAXN];//节点重量，父节点，节点深度，重儿子 void addedge(int u,int v){ static int edgeid=1; // 边的索引 // es[edgeid].to=v; // 记录目标顶点 // es[edgeid].next=head[u]; //将新边记录在u点的边的链表头部 es.push_back({v,head[u]}); head[u]=edgeid++; //更新头部 } //---------以下是dfs剖分过程 void dfshld(int u,int f){ size[u]=1; for(int i=head[u];i!=0;i=es[i].next){ int v=es[i].to; if(v==f) continue; dep[v]=dep[u]+1; fa[v]=u; dfshld(v,u); size[u]+=size[v]; if(size[v]>size[son[u]]){ son[u]=v; } } } int top[MAXN],id[MAXN],rev[MAXN]; //链头，id：当前节点在序列中的编号，rev：当前这个编号对应的是第几个节点 int total=0; void dfspos(int u,int t){ top[u]=t; //将u的链头标记到t id[u]=++total; //当前节点是序列中的total节点 rev[total]=u; //当前total节点是u if(!son[u]) return ; dfspos(son[u],t); //沿着重儿子进行dfs for(int i=head[u];i!=0;i=es[i].next){ //将其他儿子也存放到线性序列中 int v=es[i].to; if(v!=fa[u]&&v!=son[u]){ dfspos(v,v); } } } //---------以上是dfs剖分过程 //---------以下是线段树构造过程 struct node{ int l,r; int mx; int sum; int lazy; } tree[MAXN]; void build(int fat,int left,int right){ //构造线段树 tree[fat].l=left; tree[fat].r=right; if(left==right){ //刨分后fat对应的节点的值 val[rev[fat]] tree[fat].mx=tree[fat].sum=val[rev[fat]]; return; } int mid=(left+right)/2; build(fat*2,left,mid); build(fat*2+1,mid+1,right); tree[fat].mx=max(tree[fat*2].mx,tree[fat*2+1].mx); tree[fat].sum=tree[fat*2].sum+tree[fat*2+1].sum; } void pushdown(int fat){ // 推动惰性标记 int l=fat*2,r=fat*2+1; if(tree[fat].lazy!=0){ //更新左子树最值与和 tree[l].mx+=tree[fat].lazy; tree[l].sum+=(tree[l].r-tree[l].l+1)*tree[fat].lazy; //更新右子树最值与和 tree[r].mx+=tree[fat].lazy; tree[r].sum+=(tree[r].r-tree[r].l+1)*tree[fat].lazy; //推动标记 tree[l].lazy+=tree[fat].lazy; tree[r].lazy+=tree[fat].lazy; tree[fat].lazy=0;//归零 } } int maxnum=-999999,sum=0; void query(int fat,int left,int right) { //推动惰性标记 pushdown(fat); //查找区间内的最值或总和 if(tree[fat].l>=left&&tree[fat].r<=right){ maxnum=max(maxnum,tree[fat].mx); sum+=tree[fat].sum; return ; } int mid=(tree[fat].l+tree[fat].r)/2; if(left<=mid) query(fat*2,left,right); if(right>mid) query(fat*2+1,left,right); } void update(int fat,int left,int right,int val){ //推动惰性标记 pushdown(fat); //修改区间值 if(tree[fat].l>=left&&tree[fat].r<=right){ tree[fat].sum+=val*(right-left+1); tree[fat].mx+=val; return ; } int mid=(tree[fat].l+tree[fat].r)/2; if(left<=mid) upfate(fat*2,left,right,val); if(right>mid) upfate(fat*2+1,left,right,val); } //---------以上是线段树构造过程 //---------以下是解题过程 void updatexyz(){ } int getxy(int u,int v){ int sumuv=0; while(dep[top[u]]!=top[v]){//不在一条链上 if(dep[top[u]]<dep[top[v]]) swap(u,v);//保证u深 query(1,id[top[u]]+1,id[u]); sumuv+=sum;//累加 u=fa[top[u]];//将u点移动到它的父节点的链上去 } if(dep[top[u]]<dep[top[v]]) swap(u,v);//保证u深 query(1,id[u],id[v]); sumuv+=sum; return sumuv; } vector<int> ids;//存储子树节点在线段树的位置 void findids(int root){ ids.push_back(id[root]); for(int i=head[root];i;i=es[i].next){ int v=es[i].to; if(v==fa[root]) continue; findids(v); } } void updatexz(int root,int val){ findids(root); for(int i=0;i<ids.size();i++){ update(1,ids[i],ids[i],val); } } int getx(){ } //---------以上是解体过程 int main(){ cin>>n>>m>>r>>p; for(int i=1;i<=n;i++) cin>>val[i]; for(int i=1;i<n;i++){ cin>>u>>v; addedge(u,v); addedge(v,u); } dfshld(r,0); dfspos(r,r); build(1,1,n); while(m--){ cin>>c; switch(c){ case 1: cin>>x>>y>>z;//x～y的路径节点值增加z updatexyz(x,y,z); break; case 2: cin>>x>>y;//x～y的路径节点和 cout<<getxy(x,y)<<endl; break; case 3: cin>>x>>z;//x的子树节点增加z updatexz(x,z); break; case 4: cin>>x;//x的子树节点和 cout<<getx(x)<<endl; break; } } return 0; } (责任编辑：admin) |