Codeforces 1046B

题意

给你一张 $n$ 个点 $m$ 条边的无向图，满足每一个简单环上的点两两有边

$q$ 次询问两个点之间的最短路

$n\le 10^5,m\le510^5,q\le210^5$

Codeforces 487E

题意

给你一张 $n$ 个点 $m$ 条边的无向图，每个点有点权，$q$ 次操作

1. C a w，将第 $a$ 个点的权值改为 $w$

2. A a b，询问 $a$ 到 $b$ 所有可能的简单路径上的点权最小值

简单路径即不经过一个点超过一次的路径

$n,m,q\le 10^5$

LOJ #2269

题意

你有一棵$n$个点的树，点$y$有一个$[0,m)$内的整数权值$a_u$

定义一棵树的权值是点权的异或和

有$q$次操作

• Change x y，表示把第$x$个点的权值改成$y$

• Query x，表示询问有多少个非空的联通子树的权值是$x$，模$10007$

$n,q\le30000,m\le128$

引入

在有些dp中，转移可以用一种具有结合律的变换描述，并且可以快速合并

因此我们使用数据结构维护，来支持修改并快速得到全局或某个子结构的dp值

SPOJ QTREE

题意

你有一棵$n$个点的树，边有权，有两种操作

• CHANGE x y，表示修改第$x$条边的边权为$y$

• QUERY x y，表示询问点$x$到$y$路径上的边权最大值