「Codeforces 1046B」Hyperspace Highways
题意
给你一张 \(n\) 个点 \(m\) 条边的无向图,满足每一个简单环上的点两两有边
\(q\) 次询问两个点之间的最短路
\(n\le 10^5,m\le5*10^5,q\le2*10^5\)
给你一张 \(n\) 个点 \(m\) 条边的无向图,满足每一个简单环上的点两两有边
\(q\) 次询问两个点之间的最短路
\(n\le 10^5,m\le5*10^5,q\le2*10^5\)
给你一张 \(n\) 个点 \(m\) 条边的无向图,每个点有点权,\(q\) 次操作
C a w
,将第 \(a\)
个点的权值改为 \(w\)
A a b
,询问 \(a\)
到 \(b\)
所有可能的简单路径上的点权最小值
简单路径即不经过一个点超过一次的路径
\(n,m,q\le 10^5\)
你有一棵\(n\)个点的树,点\(y\)有一个\([0,m)\)内的整数权值\(a_u\)
定义一棵树的权值是点权的异或和
有\(q\)次操作
Change x y
,表示把第\(x\)个点的权值改成\(y\)
Query x
,表示询问有多少个非空的联通子树的权值是\(x\),模\(10007\)
\(n,q\le30000,m\le128\)
在有些dp中,转移可以用一种具有结合律的变换描述,并且可以快速合并
因此我们使用数据结构维护,来支持修改并快速得到全局或某个子结构的dp值
你有一棵\(n\)个点的树,边有权,有两种操作
CHANGE x y
,表示修改第\(x\)条边的边权为\(y\)
QUERY x y
,表示询问点\(x\)到\(y\)路径上的边权最大值