估:100+61+0=161
实:50+56+0=156
T1:染色大战
给出一个矩阵以及每个格子的颜色(n,m<=1000,颜色编号<=10^6)
设联通块内格子可以走相邻的颜色相同的格子到达其他格子
q个询问，每次将1所在联通块的颜色改为x，并询问新联通块的大小
可知每次更新，原联通块内的格子是不会被踢出联通块的，只需考虑有哪些点要加入联通块
可以记录下联通块相邻的同种颜色的格子位置，每次改颜色便将对应颜色的所有要加入的格子加入，并且搜索其相邻格子，颜色不同的记录下，相同的加入联通块，并递归进去继续搜索
最多会搜索nm次，时间没问题
由于初始联通块大小只计算了(1,1)，因此挂了50分(悲)
T2:树的重心
给出一棵树及其点权，求其包含的所有点数为k的联通块的第一重心点权和
（当联通块有两个重心，设第一重心为编号较小那个，否则为唯一重心）
简单树形dp可以nk^2得56分
菊花图和链形都不难想，但链形没时间打了，此外挂了k=2的子任务
ps:破案了，k=2时因为一些细节方案数传不下去，答案会错
将dp优化为nk即可AC【微笑】
T3:随机的排列
给出一个排列p，对于任意两个点i,j，令l=min(i,j)，r=max(i,j)，如果pi>pj且对于任意l<x<r满足px<pj，则在i,j间加入有向边
设一个点被覆盖当且仅当本身为关键点或被关键点指向
每次询问交换Px,Px+1，求覆盖此图所需最少关键点数
不会
完全不会
没做出T2，不过可以再高点分，下次如果能码快点能更好，最好再检查一下