乐乐做了个梦，梦见自己当了国王，乐乐王国有N座城市，乐乐王国的道路构成树状结构：首都1与几个大城市相连，这几个大城市又通过道路与一些稍小的城市相连……严格地说，这N座城市构成一棵有根树，城市i的管理区域为以i为根的子树，道路都是双向的，经过每条道路需要收费，从城市A到城市B的花费为A到B的简单路径上所有道路的费用之和，显然，一棵树上任意两点之间的简单路径是唯一的。
乐乐做了个梦，梦见自己当了国王。乐乐王国有N座城市（编号从1~N，首都的编号为1）。乐乐王国的道路构成树状结构：首都1与几个大城市相连，这几个大城市又通过道路与一些稍小的城市相连……严格地说，这N座城市构成一棵有根树（1为树根），城市i的管理区域为以i为根的子树。 道路都是双向的。经过每条道路需要收费，从城市A到城市B的花费为A到B的简单路径上所有道路的费用之和（不妨称之为城市对(A, B)之间的花费）。显然，一棵树上任意两点之间的简单路径（即不能重复经过某个点的路径）是唯一的。 由于物价飞涨，经过一番缜密的思考，乐乐决定重新规划自己国家的道路收费。具体来说，他要进行Q个操作，每个操作是如下两种类型： INC u v w ——表示u到v的路径上，所有的道路的收费增加w； ASK p ——表示询问城市p的管理区域中，所有的“城市对”的花费之和。比如，城市p的管理区域（即以p为根子树）中有城市c1, c2, c3, …，cs（这里面包括p），询问所有的城市对(c1, c2), (c1, c3), …, (c2, c3), …,(cs-1, cs)的花费之和。 乐乐把这个问题交给你，快帮帮他吧！
（图片来源网络，侵删）
标签： HBC17494未来城市规划题解
