ming专题

HDU 5614 Baby Ming and Matrix tree (树链剖分)

题意: 一颗树上,树上每个点是一个2×2的01矩阵(每个矩阵有两个1和两个0),可以顺时针旋转这个矩阵旧时度(代价2),或者直接替换(代价10),每次给你一个v,u和一个矩阵,问v到u的路上的矩阵全部变成刚给的矩阵的最小代价 思路: 树链剖分,因为1有两个,所以只有6种矩阵(其中又可以分成两组,每组中的矩阵可以相互转换),那么我们把矩阵手动手动标号,算出转换最小代价,然后用6棵线段树暴力查询