题目链接
这题居然没有想到乘法原理…还是要多想想乘法原理啊…

先dfs出$siz_i$为每个点子树大小。然后对每个边算次数。根据乘法原理，次数为$siz_i \times (n-siz_i)$，那么这条边对答案的贡献为$val \times siz_i \times (n-siz_i)$，然后就可以求了。

注意开long long，而且乘法会溢出所以要在中途每个强制转换

题目链接
原图要求一个分值最大的斜正方形，斜着不好弄，那就倒过来。
把矩阵旋转$45^{\circ}$，然后就可以直接水平求正方形了。
具体怎么旋转看我的另一个博文。这里注意旋转以后的数组有些地方不可用，可能会敲到棋盘外，也有可能敲到边上，在输入的时候用一个数组记录一下就好，注意数组比较大，不要MLE了.
顺便附上使用了前缀和优化的暴力，考试时拿了90分，不能相信…

Bzoj 1084
$m$只有$1, 2$，分情况讨论：
$m=1​$时，就是一个简单的最大连续子段和，设$dp(i,j)​$为前$i​$个数分了$j​$段的最优值
则有$dp(i,j)=max(dp(i-1, j), dp(k,j-1)+S_{i}-S_{k})$，其中$S$是前缀和。
$m=2$时，我们设$dp(i,j,k)​$为第一列前$i$个数第二列前$j$个数分了$k$个矩阵的最优值
则$dp(i,j,k)=max(dp(i-1,j,k), dp(i,j-1,k), dp(l, j, k-1)+S1_i - S1_l, $
$dp(i, l, k-1)+S2_i - S2_l)$，其中$S1$是第一列前缀和，$S2$是第二列前缀和。
当$i=j$时，还可以选择两列一起的大矩阵，则$dp(i,j,k)=max(dp(l,l,k-1)+S1_i+S2_j-S1_l-S2_l)$
初始都要赋值为$-INF$，但是当$j=0$时要赋值为$0$，不然就会导致答案负数。

BZOJ 1491
之前一直想dij/SPFA，被次短路的思路越扯越远…看见$n$才$100$那就应该想Floyd啊。。题目挺水虽然说NOI原题。。
Floyd时顺便求路径条数，用乘法原理$num(i,j)=num(i,k) \times num(k,j)$，相同的时候不要忘了加上$num(i,k) \times num(k,j)$
之后再扫一次，找每个中转点$k$，然后继续用乘法原理，经过$k$点的路径总数为$num(i,k) \times num(k,j)$，然后统计一下就出来了

模板及讲解

一份资料

拆点

把一个点拆成两个点比较简单不多说
例题: NOIP2010 T3

带权

例题: NOIP2010 T3
并查集维护一个$r$数组，表示$i->father(i)$的权值。
定理：一个并查集中从一个点出发，沿着它所指向的边一直走，并累加下路上的权值(如果边是反的那么就取权值的负数)，走一圈回来，累加的和模 最大值$+1$ 结果一定是$0$
路径压缩：

由图，根据敌人的敌人是朋友(多于两个阵营不适合带权并查集)，新的$r_x$的值就是$(r_x+r_{f_r})\%(MaxWeight+1)$

合并的情况：$father(y)=x$，$x$是$a$的根，$y$是$b$的根

由图，$(k+r_b+r_y-r_a)\%(MaxWeight+1)=0$，因为$y$合并至$x$，所以$r_y$变了，那么我们就算出$r_y$即可，$r_y=(-k-r_b+r_a+MaxWeight+1)\%(MaxWeight+1)$，其中加上$MaxWeight+1$是为了防止负数。
查询的情况(在一个集合)

由图，如果$(k+r_b-r_a+MaxWeight+1)\%(MaxWeight+1)=0$的话，那么$a->b$就是$k$，我们就可以这样判断关系。

可撤销并查集

可以回退的并查集，复杂度大约$(logn)$
不能路径压缩，所以只能按秩合并 (启发式合并，siz小的合并到大的)
每次合并记录合并的两个点放到栈中，然后撤销时用栈顶来依次撤销

按秩合并:

void mg(int a, int b) {
    int x = a, y = b;
    if (sz[x] > sz[y]) swap(x, y);
    f[x] = y, sz[y] += sz[x], s.push(mp(x, y));
}

撤销操作：

void cc(int tms) {
    while (tms-- && !s.empty()) {
        pair<int, int > p = s.top(); s.pop();
        int x = p.fir, y = p.sec;
        f[x] = x, sz[y] -= sz[x];
    }
}

维护信息

一般可以维护$size$等信息。
例题：Luogu 1196
本题需要维护$d_i$表示$i$到根有多少个战舰和$size$。
查询输出$abs(d_x - d_y)-1$即可。

维护只删除链表 ( 跳过序列某一个值 )

通过让$x$成为$x-1$的儿子来删掉$x$位置，查询时$x$的根为他左边的第一个位置。
例题：Poj 1456
通过让$x$成为$x+1$的儿子来删掉$x$位置，查询时$x$的根为他右边的第一个位置。
例题：Bzoj 2054

维护数组(维护差分约束)

在$find$时，先递归$t=find(f(x))$，然后维护值，然后再使$f(x)=t$
差分约束：用并查集维护$c_i=s_i-s_{rt}$
例题: BZOJ 1202

网格图维护行列

在维护行列的并查集中，如果$r_i$与$c_i$连通则网格这个点被染色，整个图是连通的网格则所有点都被染色。
例题: Codeforces 1013D

BZOJ 1202
方法一：
用并查集维护前缀和的差值。设前缀和$s_i$，$c_i$为$s_i-s_{rt}$的值($rt$是这个并查集的根)。

每次查询，如果$x-1,y$属于一个集合，那么直接查询$c_y-c_{x-1}$。
证明：$s_y=c_y+s_{rt}, s_{x-1}=c_{x-1}+s_{rt}$，那么$s_y-s_{x-1}=c_y+s_{rt}-(c_{x-1}+s_{rt})=c_y-c_{x-1}$。

如果不在一个集合，那么直接合并，$father(rtx)=rty$，($rtx$是$x-1$的根, $rty$是$y$的根)，这个时候$c_{rtx}$改变了，$c_{rtx}=c_y-c_{x-1}-v$。
证明：$s_{rty}=s_y-c_y, s_{rtx}=s_{x-1}-c_{x-1}$
$c_{rtx}=s_{rtx}-s_{rty}$
$=s_{x-1}-c_{x-1} - (s_y-c_y)$
$=-(c_{x-1}-c_y)-(s_{y}-s_{x-1})$
$=c_y-c_{x-1}-v$

方法二：
用差分约束维护前缀和，设前缀和$s_i$。
由题意得$s_y-s_{x-1}=v$
将不等式规范化，得$s_y-s_{x-1}\leq v, s_y-s_{x-1}\geq v$
即$s_y-s_{x-1}\leq v, s_{x-1}-s_{y}\leq -v$
然后用SPFA检查是否有解

BZOJ 1303
因为题目是$1-n$排列，所以$b$只会出现一次，那么我们记录$b$的位置$p$，然后我们不难发现当$b$旁边连续的几个数中大于$b$和小于$b$的数的个数相同就会对答案作出贡献。我们记录左边大于$b$的数为$1$，小于$b$的数为$-1$，也就是差分序列(括号序列)，然后从$p-1$到$1$求前缀和，记录在$sum$中，然后$l$数组就是记录某个前缀和出现的次数。右边同理，但是大于$b$的数为$-1$，小于$b$的数为$1$。然后根据乘法原理，左边有$l_i$个可匹配，右边有$r_i$个可匹配，答案就是$\sum_{i=-n}^n l_ir_i$，负数要处理一下，加一个常数，但是注意数组的大小就要乘以二了.

Bzoj 1192
很容易发现把$m$转为二进制，所需要的袋数就是二进制的位数
这里有一个特别重要的：二进制下两个$2$的平方数的位数是不变的。并且这中间的所有数都可以由这几位二进制表示。

BZOJ 1003
这种最优性很难考虑的优先思考DP。
我们可以算出$c(i,j)$为$i$天到$j$天都能走过的最短路。读入不可以走的数据可以存在一个数组里(类似桶)直接查询，然后每次SPFA的时候预处理出哪些点不可以走，之后再做最短路，然后设$dp(i)$为前$i$天的最小费用，则转移方程
$dp(i)=min(dp(j)+c(j+1,i)+k)$
其中初值定为$dp(i)=c(1,i)$，然后本题就解决了，注意$n$和$m$所表示的数量意义，不要把顶点数弄成$n$了。

BZOJ 1002
由基尔霍夫矩阵树定理推出递推式
$$dp(n)=3dp(n-1)-dp(n-2)+2$$
初值$dp(1)=1, dp(2)=5$，然后答案很大需要高精度，这题也作为一个练习高精度的题目了