{"problem":{"name":"BZOJ3159 决战","description":{"content":"Katharon 国有 $n$ 个城市，编号为 $1\\sim n$。出于勤俭节约，不铺张浪费的考虑，城市间只连有 $n-1$ 条道路，使得可以从一个城市出发沿着道路走到另一座城市。 现在 X 国的飞船降落在了某个城市，并把它改造成了自己的据点。X 国占领其他国家的一贯做法是，在据点里造一堆工厂生产战斗机器人，然后沿着被侵略国的道路运送到其他城市。X 国的司令向来不走回头路，而且崇尚团结与绝对的公","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10659"},"statements":[{"statement_type":"Markdown","content":"Katharon 国有 $n$ 个城市，编号为 $1\\sim n$。出于勤俭节约，不铺张浪费的考虑，城市间只连有 $n-1$ 条道路，使得可以从一个城市出发沿着道路走到另一座城市。\n\n现在 X 国的飞船降落在了某个城市，并把它改造成了自己的据点。X 国占领其他国家的一贯做法是，在据点里造一堆工厂生产战斗机器人，然后沿着被侵略国的道路运送到其他城市。X 国的司令向来不走回头路，而且崇尚团结与绝对的公平，因此运送战斗机器人时，会先选择一个终点，再在从据点到终点的路径上选择一个起点，然后把机器人均匀分配到起点到终点路径上的每个城市。同时，为了重新分配机器人，X 国的司令还会下令，按照与运送机器人相同的方法选择起点和终点，然后翻转这条路径上城市的机器人的数量。比如，选定的路径上的城市的机器人数依次为 $1,2,3,4,5$，翻转之后就变成了 $5,4,3,2,1$。\n\nKanari 国王手中的圆盘上浮现出了 Katharon 国的地图。不仅如此,上面还标出了 X 国据点在 $r$ 号城市，并显示出了 X 国司令刚刚下达的指令。“太好了！”国王欢呼，“我们能第一时间掌握敌人的布局，就一定能击退 X 国的侵略者！”\n\n但是还有一个问题没有解决。圆盘上只显示了指令，却没有标出每个城市的机器人数量，这让国王很是头疼。于是他找到了你，想让你帮忙设计一个程序来回答国王的询问。国王只关心某两个点之间路径上的城市的机器人和、最大值以及最小值，以便确定兵力部署、攻击要点和敌方的薄弱点。\n\nX 国司令的指令和 Kanari 国王的询问如下：\n\n1. `Increase x y w` 运送一批机器人到从 $x$ 到 $y$ 的路径上的城市，并分配给每个城市 $w$ 个机器人；\n2. `Sum x y` 询问从 $x$ 到 $y$ 的路径上的城市的机器人数量之和。\n3. `Major x y` 询问从 $x$ 到 $y$ 的路径上的城市的机器人数量的最大值。\n4. `Minor x y` 询问从 $x$ 到 $y$ 的路径上的城市的机器人数量的最小值。\n5. `Invert x y` 翻转从 $x$ 到 $y$ 的路径上的城市的机器人数量。\n\n对于 X 国司令的指令，保证给定的 $x,y$ 满足上文所述的要求。对于 Kanari 国王的询问，**不**保证给定的 $x,y$ 满足上述要求。\n\n## Input\n\n第一行有三个整数 $n,m,r$，分别表示树的节点数、指令和询问总数，以及 X 国的据点。\n\n接下来 $n-1$ 行，每行两个整数 $x$ 和 $y$，表示 Katharon 国的一条道路。\n\n接下来 $m$ 行，每行描述一个指令或询问，格式见题目描述。\n\n## Output\n\n对于每个询问操作，输出所求的值。\n\n[samples]\n\n## Note\n\n数据保证，$1\\leq n,m\\leq 5\\times 10^4$，且对于运送操作 $1\\leq w\\leq 10^3$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10659","tags":["平衡树","O2优化","树链剖分","动态树 LCT"],"sample_group":[["5 8 1\n1 2\n2 3\n3 4\n4 5\nSum 2 4\nIncrease 3 5 3\nMinor 1 4\nSum 4 5\nInvert 1 3\nMajor 1 2\nIncrease 1 5 2\nSum 1 5","0\n0\n6\n3\n19"]],"created_at":"2026-03-03 11:09:25"}}