「UOJ 345」「清华集训2017」榕树之心
题目背景
深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。
……
深秋。冷风吹散了最后一丝夏日的暑气，也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧，石桥依旧，榕树虽是历经荣枯更迭，依旧亭亭如盖，只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。
……
AGC005E - Sugigma: The Showdown
有 \(n\) 个点，\(n-1\) 条红边和 \(n-1\) 条蓝边分别把这些点连成一棵树
一开始第一个人在 \(x\)，第二个人在 \(y\)，第一个人先手，轮流操作
第一个人走红边，第二个人走蓝边，每次操作可以不动或走一条边。
当两个人相遇的时候游戏结束，第一个人希望最大化总步数，第二个人希望最小化，两个人绝顶聪明
问游戏能否结束，如果可以结束输出最后的步数
本题包含三个问题：
问题 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\)
给你一张 \(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值