UOJ #345. 【清华集训2017】榕树之心

题目背景

深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。

……

AGC005E - Sugigma: The Showdown

题意

有 $n$ 个点，$n-1$ 条红边和 $n-1$ 条蓝边分别把这些点连成一棵树

一开始第一个人在 $x$，第二个人在 $y$，第一个人先手，轮流操作

第一个人走红边，第二个人走蓝边，每次操作可以不动或走一条边。

当两个人相遇的时候游戏结束，第一个人希望最大化总步数，第二个人希望最小化，两个人绝顶聪明

问游戏能否结束，如果可以结束输出最后的步数

LOJ #2983. 「WC2019」数树

题意

本题包含三个问题：

• 问题 0：已知两棵 $n$ 个节点的树的形态。要给予每个节点一个 $[1, y]$ 中的整数，使得对于任意两个节点 $p, q$，如果存在边 $(p, q)$ 同时属于这两棵树，则 $p, q$ 必须被给予相同的数。求给予数的方案数。

• 问题 1：已知第一棵树，对于第二棵树的所有 $n^{n−2}$ 种选择方案，求问题 0 的答案之和。

• 问题 2：对于第一棵树的所有 $n^{n−2}$ 种选择方案，求问题 1 的答案之和。

对 $998244353$ 取模

Codeforces 1097G. Vladislav and a Great Legend

当时不会做

题意

给定一棵 $n$ 个点的树

对于每个非空的点集 $X\subseteq {1,2,\dotsc,n}$，定义 $f(X)$ 表示最少的能让点集 $X$ 联通的边的数量

求

$$
\sum_{X\subseteq {1,2,\dotsc,n},X\ne \varnothing} (f(X))^k
$$

模 $10^9+7$

$n\le 10^5,k\le 200$

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值

BZOJ 1023

题意

你有一棵$n$个点的仙人掌，边权为$1$

定义两点的距离是最短路的长度

定义仙人掌的直径是距离最远的两点的距离

求直径

$n\le5*10^4$

BZOJ 4316

题意

你有一棵边仙人掌，求最大点独立集

$n\le510^4,m\le610^4$