没参加比赛。。因为不是周末晚上家里没网。。。（很奇怪的性质对不对。。。

417 D 有N(<=100)个朋友，M(<=20)个题，每个朋友可以做一些题，但是你要邀请这个朋友必须要交xi元钱还有你家至少要有ki个物♂体，每个物♂体需要B元钱，问做完所有题需要多少钱。

是个N*2^M的状压dp，发现不能解决k的问题，那按照k排序，选了第一个那后面一定不用管了。

417 E 求一个N*M(<=100)的数表，使得每一行(列)的所有数的平方和加起来是个完全平方数

如果一行的数平方和加起来是个完全平方数，那把这一行的数都乘K也是一行合法的数，所以搞出一个1*N的向量和一个M*1的向量，乘起来显然是一组合法答案。构造向量的方法有很多，首先发现爆搜跑得飞快，还有一种构造方法就是

{N <= 2的时候特判；N = 2 * K, 构造1,1,..,1,K-1；N = 2 * K + 1， 构造1,1,...,1,2,K+1；}可以发现跟爆搜一样。。

418 D 一棵树(<=10^5)每次询问(<=10^5)两个点，每个点的最短路定义为到这两个点中短的那个，求所有点最短路中最大的那个。

据说是原题。。对于一个询问(u,v)可以沿其路径中点把树切成两部分，一部分到u最短，一部分到v最短，设到(u,v)lca长的那个是u，那么u那一部分的最远点就是一个点到u的距离+这个点子树中不走含u的路径中最远的那个，v那一部分也大概是这样，所以可树形dp，也可以维护个dfs序考虑没走一步对两边树上答案的贡献。有修改的话可以写树套树。

当然还有一种lct的在线做法，也可以支持修改，比这个要好写的多，这里不想再多说了。。

//叉姐太屌了。。提供了一种线性做法的思路。。这里我按照我的理解摆上

一种线性的在(离)线做法：对于询问(u,v)，沿其中点切开，那么两棵树中到u(v)的最远点必然是两棵树的直径的两个端点的某一个。对于切割有这样一个性质：对于原树的一个直径，如果我们没有切开它，那么答案肯定是直径到询问点的距离。那么我们可以算出切点在直径上的2*Len棵树的直径，询问的时候分类讨论。

一种线性计算这2*Len棵树直径的方法：我们先把直径上的边全部断掉，形成了Len+1棵有根(根就是在直径上的点)树的森林，一字排开，用f[i]代表第i棵树到根的最远距离(即深度)，用g[i]代表从左边开始前i棵树组成的大树的直径，t[i]代表从右边开始后i棵树组成的大树的直径，（这显然就是我们要求的2*Len棵树的直径）。

对于g[i]，f[i]的意义变为从左边开始前i棵树组成的大树的且以i为根的最大深度

转移方程：g[i] = max(g[i-1],f[i]+f[i-1]+1)，f[i] = max(f[i], f[i-1]+1)

大概是这样，如果不对自己yy一下就好了。。反正能线性。。。

于是我们求出来了要的东西。。现在只需要一个线性的在(离)线的lca就可以了，询问的时候如何判断切点是不是在直径上呢。又需要分类讨论了。。如果我们以直径的一个端点为根建一棵树，如果(u,v)的切点在直径上，首先他们的lca一定在直径上了。。之后就是距离的问题了。。首先线性预处理每个点到直径的距离是可以做到的。。然后就是一系列什么dist(u->Diameter), dist(u->lca), dist(v->Diameter)的判断。。总之很恶心就是了。。

要是不做到O(N)。。那我介绍这个东西也就没意义了！！总之很恶心。。。。以上。。。

418 E 题意是定义一个N(<=10^5)列无穷行的数表，第一行是固定的，之后第x行y列的数定义为：第x-1行第y列的数在第x-1行前y列中出现的次数。要求支持把第一行p(<=N)列的数修改为v(<=10^9)，查询第x(<=10^5)行y(<=N)列的数两个操作。

打了个表找规律。。(?)发现有循环节，当然还有更简单的证明：

附一段聊天记录。。

//////