P2590 树的统计题目解析-北京尧图网络

一题面一棵树上有 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 本身。对于每个QMAX或者QSUM的操作每行输出一个整数表示要求输出的结果二理解考虑线段树结合树链剖分按照顺序梳理1输入树dfs1函数得出基本信息即 fa每个点的父节点 sz每棵子树大小 depth深度 maxson每个点的重孩子进行重链剖分2dfs2划分重链1得出3个新基本信息即 top每个点所在链的链头 dfn每个点的dfs序 fn每个dfs序所对应的点的编号2分链重孩子的链头自己链头轻孩子单开一条链3对dfs序构建线段树 dfs序通用性质把树压成一维数组同一条重链上所有节点的dfn编号是一段连续区间可以把树上路径转成线段树区间任意两点路径能够拆成多段连续区间所以可以使用线段树维护树上路径其中pushupbuild普通对于线段树查询的query和update均为模板代码4对于链查询的query_chain 求LCA模板代码如下其中跳链步骤与之相同int LCA(int x,int y) { while(top[x]!top[y]) { if(depth[top[x]]depth[top[y]]) swap(x,y); xfa[top[x]]; } if(depth[x]depth[y]) return x; else return y; }借助条链把 x 到 y 的树上路径拆成若干条完整重链最后同链的一段三代码详细解析在注释#includebits/stdc.h #define ll long long using namespace std; const int N3e45; int a[N],fn[N],fa[N],sz[N],depth[N],dfn[N],top[N],maxson[N],tot,ans,n,q; struct node { int L,R,maxx,sum; } st[N2]; vectorint g[N]; void pushup(int root) { st[root].maxxmax(st[root1].maxx,st[root1|1].maxx); st[root].sumst[root1].sumst[root1|1].sum; } void build(int root,int L,int R) { st[root].LL; st[root].RR; if(LR) { st[root].maxxst[root].suma[fn[L]];//注意对dfs序打线段树要反映射回编号 return ; } int midLR1; build(root1,L,mid); build(root1|1,mid1,R); pushup(root); } void update(int root,int L,int R,int k,int val) { if(LR) { st[root].maxxst[root].sumval; return ; } int midLR1; if(kmid) update(root1,L,mid,k,val); else update(root1|1,mid1,R,k,val); pushup(root); } void dfs1(int u,int f) {//作用求重儿子、sz、depth、fa fa[u]f,sz[u]1,depth[u]depth[f]1; for(int v:g[u]) { if(vf) continue; dfs1(v,u); sz[u]sz[v]; if(!maxson[u]||sz[maxson[u]]sz[v]) { //v是否是u的重孩子 maxson[u]v; } } } void dfs2(int u,int t){//作用划分重链 t即为此时u点对应的链头 top[u]t; dfn[u]tot; fn[tot]u;//反映射标记dfs序对应的编号 if(maxson[u]){//有重孩子优先走重孩子 dfs2(maxson[u],t);//链头不变重孩子自动成链 for(int v:g[u]){ if(v!maxson[u]v!fa[u]){//是轻孩子不重走 dfs2(v,v);//轻孩子单开链链头是自己 } } } } int query(int root,int L,int R,int l,int r,int type){ if(type1){ if(lLRr){ return st[root].maxx; } int midLR1; if(rmid) return query(root1,L,mid,l,r,type); else if(lmid) return query(root1|1,mid1,R,l,r,type); else return max(query(root1,L,mid,l,r,type),query(root1|1,mid1,R,l,r,type)); } else{ if(lLRr){ return st[root].sum; } int midLR1; if(rmid) return query(root1,L,mid,l,r,type); else if(lmid) return query(root1|1,mid1,R,l,r,type); else return query(root1,L,mid,l,r,type)query(root1|1,mid1,R,l,r,type); } } int query_chain(int x,int y,int type) { if(type1) ans-0x3f3f3f3f; else ans0; while(top[x]!top[y]) { if(depth[top[x]]depth[top[y]]) swap(x,y); int tmpquery(1,1,n,dfn[top[x]],dfn[x],type);//路径的一部分 if(type1) ansmax(ans,tmp); else anstmp; xfa[top[x]];//跳到不同的链直到共链 } if(depth[x]depth[y]) swap(x,y); int tmpquery(1,1,n,dfn[y],dfn[x],type);//对dfs序打线段树此时跳完后的x和y共链,这是最后的那部分路径 if(type1) ansmax(ans,tmp); else anstmp; return ans; } int main() { scanf(%d,n); for(int i1; in; i){ int aa,bb; scanf(%d%d,aa,bb); g[aa].push_back(bb); g[bb].push_back(aa); } for(int i1;in;i) scanf(%d,a[i]); dfs1(1,0); dfs2(1,1);//1的链头是自己 build(1,1,n); scanf(%d,q); while(q--){ char op[10]; int x,y; scanf(%s%d%d,op,x,y); if(op[0]C){ update(1,1,n,dfn[x],y);//对dfs序打的线段树所以找的是dfn[x] } else{ if(op[1]M){ printf(%d\n,query_chain(x,y,1)); } else{ printf(%d\n,query_chain(x,y,0)); } } } }好久没干这活了大肘子欢迎指正

P2590 树的统计题目解析

相关推荐

AI艺术生成器技术解析：从扩散模型到提示词工程实战指南

Java 17 + JUnit 5 黑盒测试实战：三角形问题决策表从16条到8条的化简逻辑

2026年建站工具对比：谁更懂“零门槛建站”？

更多资讯

AI Agent 智能体实战：任务拆解、工具调用与结果校验闭环

WinDbg(x86)蓝屏日志分析实战：从符号配置到驱动定位

GaussDB 5.0轻量级安装包Linux部署指南：从环境核对到参数调优

本地AI项目从0到1部署跑通：环境自检、接口验证与批量任务实操清单

Mycat 1.6.7.1 CentOS 7 分库分表实战指南

Linux网桥brctl实战：编译、STP调参与iproute2迁移

今日更新

Agent-Reach：打通大模型触达外部系统的最后一公里

深度学习图像隐写分析实战：从CNN原理到毕设源码全解析

AI赋能知识产权供需匹配：专利评估、需求挖掘与多路召回工程实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？