greedy
3s, 1024MiB
题目描述
给定一棵 $n$ 个节点带边权的有根树， 根节点为 $1$。
定义：
- $dis(u,v)$ 表示 $u$ 到 $v$ 的路径上的边权和（$u=v$ 则为 $0$）。
- $sub(u)$ 表示 $u$ 子树内的点所成的集合。
你需要执行以下三种操作 $q$ 次：
1 u v将树链 $u,v$ 上的边权变为原本的相反数（$u=v$ 则不操作）。2 x u询问 $\min_{v\in sub(x)} dis(u,v)$。3 x y询问 $\min_{u\in sub(x)}\min_{v\in sub(y)}dis(u,v)$。
输入格式
第一行两个整数 $n,q$。
接下来 $n-1$ 行， 第 $i$ 行两个整数 $f_i,w_i$， 表示 $i$ 的父亲以及其到父亲的边的长度。
接下来 $q$ 行，每行三个整数代表一次操作。 保证至少有一次 $2$ 或 $3$ 操作。
输出格式
对于每个 $2$ 或 $3$ 操作， 输出一行一个整数表示答案。
【样例 1】
【样例 1 输入】
3 3
1 114
1 514
2 1 2
1 1 3
2 1 2【样例 1 输出】
0
-400数据范围
对于 $100\%$ 的数据， 满足 $1\leq n,q\leq 2\times 10^5,1\leq f_i< i,-10^9\leq w_i\leq 10^9$。
| 测试点编号 | $n,q\leq$ | $f_i=i-1$ |
|---|---|---|
| $1,2$ | $100$ | |
| $3\sim 5$ | $3000$ | |
| $6,7$ | $10^5$ | ✔ |
| $8,9$ | $10^5$ | |
| $10\sim 12$ | $10^5$ | ✔ |
| $13\sim 15$ | $10^5$ | |
| $16,17$ | $2\times 10^5$ | ✔ |
| $18\sim 20$ | $2\times 10^5$ |
其中：
- $6,8$ 测试点只有 $2$ 操作。
- $7,9$ 测试点只有 $3$ 操作。
- $10,13$ 测试点没有 $1$ 操作。
- $11,14$ 测试点没有 $2$ 操作。
- $3,12,15$ 测试点没有 $3$ 操作。