版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [CodeForces 696 A] Lorenzo Von Matterhorn" categories:

题目链接

<!-- more -->

简述题意

给出一棵完全二叉树, 对其上任意结点 $i$, 其子结点只能为 $2i$ 和 $2i+1$, 其父结点只能为 $\lfloor\frac{i}{2}\rfloor$

处理两种操作

  1. 1 u v w: 将从u到v的最短路径经过的所有边加上权值w (权值不影响路径长度)
  2. 2 u v: 统计从u到v的最短路径经过的所有边权值之和

解题思路

对于树来说, 实现这两种操作我们自然会想到 LCA 之类的, 不过这道题有一个巧妙的解法可以绕过这些知识

我们用一个map来记录权值的变化, 在更新和查询权值时, 我们从u, v向上查找, 直到到达了lca(u, v)为止

由于这是在完全二叉树上, 我们并不需要去求lca(u, v), 我们只需这样: 在每次循环的时候选u和v中编号较大的那个, 一边维护一边向上回溯, 当u和v相等的时候我们就已经维护到了lca(u, v), 题目自然就解决了

代码

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:CodeForces_696A CodeForces/696A/0.cpp %} </details>