提高组模拟赛总结
Scinerely
·
·
个人记录
| 题目名称 |
祖先 |
树上操作 |
| 总分 |
100 |
100 |
| 题目类型 |
传统 |
传统 |
| 每个测试点时限 |
1.0S |
3.0S |
| 内存限制 |
128 MB |
256MB |
比赛事项：
1.因为不是正式考试，所以考生不许要将程序开启文件输入输出。同意将文件打包至云剪贴板并将网址交在赛后讨论。（因为洛谷不允许交这么大的数据）
2.我们将会在Linux环境下评测。没有O2
3.比赛按照提高组难度编写（可能难度会比提高组简单，因为出题人水平有限）。
4.源代码长度不得大于 100KB（千万别打一个 10^8 的表交上来）。
5.T1不一定是最简单的，注意开题顺序。（友情提示：T2最水了）
6.注意IO优化，数据强度较大
因为出题人太懒了，所以题目并没有太多情景带入嘿嘿嘿
并且数据的正确性是有保障的，都是暴力程序100多秒一个（有的却很快，并且有的暴力是跑不了的比如说T1就是标称造的）跑出来的。
祖先 (Ancestors)
题目背景
「没有祖先哪来的你！」
题目描述
对于一棵深度为 dep 的满二叉树(根节点的深度为 1)，对其用 bfs 序（即层序遍历）进行编号。此时，希望求出：
\sum_{i=1}^{2^{dep}-1}\sum_{j=i+1}^{2^{dep}-1}\text{lca}(i,j) \ (\text{lca}(i,j) \ne i)
答案对 $10^9+7$ 取模。
## 输入格式
第一行，一个正整数 $dep$ 。
## 输出格式
一个整数表示答案。
## 样例 #1
### 样例输入 #1
```
3
```
### 样例输出 #1
```
14
```
## 样例 #2
### 样例输入 #2
```
114514
```
### 样例输出 #2
```
19628900
```
## 提示
对于 $20 \%$ 的数据，保证 $dep \leq 12$ 。
对于 $40 \%$ 的数据，保证 $dep \leq 20$ 。
对于 $60 \%$ 的数据，保证 $dep \leq 10^6$ 。
对于另外 $10 \%$ 的数据，保证 $dep \leq 10^9$。
对于 $100 \%$ 的数据，保证 $dep \leq 10^{16}$ 。
# 树上操作（tree）
## 题目描述
现在给定了一颗有 $n$ 个节点的树。接下来有三种操作一共 $m$ 次：
```1 u v w``` 表示将节点 $u$ ，$v$ 之间的唯一道路上的边的边权变为 $w$ 。
```2 u v``` 表示查询在节点 $u$ ，$v$ 之间的唯一道路上的边出现了多少种不同的边权。
```3 u v``` 表示查询在节点 $u$ ， $v$ 之间的唯一道路上的边权中，最长有多少条连续的边满足边权相同。
一开始，每一条边的边权都是 $0$ 。
## 输入格式
第一行，两个正整数 $n,m$ 。
接下来的 $n-1$ 行，每行两个正整数 $u,v$ ，表示存在一条连接 $u,v$ 的边。
再接下来的 $m$ 行，每行两到三个整数表述了一次操作，具体格式见题目描述。
## 输出格式
对于每一个操作二或者操作三，一行一个整数表示答案。
## 样例 #1
### 样例输入 #1
```
8 6
1 2
1 3
2 4
2 5
4 6
4 7
3 8
3 8 6
1 5 8 2
2 6 8
3 6 8
1 6 1 1
2 7 3
```
### 样例输出 #1
```
5
2
3
3
```
## 提示
对于 $30 \%$ 的数据，保证 $n,m \leq 10^3$ 。
对于另外的 $5 \%$ 的数据，保证没有操作一。
对于另外的 $25 \%$ 的数据，保证没有操作二。
对于 $100 \%$ 的数据，保证 $n,m \leq 10^5,w \leq 100$ ，并且数据随机生成。